Решение систем уравнений методом квадратного корня

Решение систем уравнений методом квадратного корня

Обсуждение и решение задач по математике, физике, химии, экономике

Часовой пояс: UTC + 3 часа [ Летнее время ]

Введение в анализ

Теория очередей (СМО)

Страница находится по новому адресу

Часовой пояс: UTC + 3 часа [ Летнее время ]

Контрольная работа: Метод квадратных корней

Система линейных алгебраических уравнений – математическая модель, которая описывает состояние равновесия экономического объекта, которое называется установившимся режимом или статикой объекта. Экономическая статика изучает допустимые и рациональные состояния экономического объекта.

Пусть дана система n линейных алгебраических уравнений с n неизвестными

или в матричной форме

— столбец свободных членов и столбец неизвестных соответственно.

Если матрица А неособенная, т.е.

то система (1.1) имеет единственное решение. В этом случае решение системы (1.1) с теоретической точки зрения не представляет труда. Значения неизвестных x_i (i=1,2,…n) могут быть получены по известным формулам Крамера

крамер квадратный корень матрица

где матрица A_i получается из матрицы А заменой ее i-го столбца столбцом свободных членов.

Но такой способ решения линейной системы с n неизвестными приводит к вычислению n + 1 определителей порядка n, что представляет собой весьма трудоемкую операцию при сколько-нибудь большом числе n.

Применяемые в настоящее время методы решения линейных систем можно разбить на две группы: точные и приближенные.

Точными методами называются такие методы, которые в предположении, что вычисления ведутся точно (без округлений), приводят к точным значениям неизвестных x_i . Так как на практике все вычисления ведутся с округлениями, то и значения неизвестных, полученные точным методом, неизбежно будут содержать погрешности. К точным методам относятся, например, метод Гаусса, метод квадратных корней.

Приближенными методами называются такие методы, которые даже в предположении, что вычисления ведутся без округлений, позволяют получить решение системы (x₁ , x₂ , …, x_n ) лишь с заданной точностью. Точное решение системы в этих случаях может быть получено теоретически как результат бесконечного процесса. К приближенным методам относятся метод простой итерации, метод Зейделя и др. Каждый из этих методов не всегда является сходящимся в применении к конкретному классу систем линейных уравнений.

Данная контрольная работа имеет следующую структуру: в начале рассматривается математическая постановка задачи для метода квадратных корней при решении систем линейных алгебраических уравнений. Затем производится реализация данного метода с помощью вычислительных средств ЭВМ, а именно прикладной программой Matlab 6.5. На примере реализации нескольких тестовых задач проводится анализ точности данного метода, а именно когда наиболее эффективно применять метод квадратных корней при решении систем линейных алгебраических уравнений. Анализ проводится на основе матрицы А (ее мерности, разреженности, обусловленности. Результаты, полученные на основе метода квадратных корней, приведены в конце данной работы. Также в работе представлен графический материал. По окончании проведения исследования работа завершается логическим заключением.

Метод квадратных корней используется для решения линейной системы

у которой матрица А симметрическая, т.е.

Метод является более экономным и удобным по сравнению с решением систем общего вида.

Решение системы осуществляется в два этапа.

Прямой ход. Представим матрицу А в виде произведения двух взаимно транспонированных треугольных матриц:

А = Т¢ Т,

.

Перемножая матрицы T¢ и T и приравнивая матрице A, получим следующие формулы для определения t_ij :

После того, как матрица Т найдена, систему (1.2) заменяем двумя эквивалентными ей системами с треугольными матрицами

Обратный ход. Записываем в развернутом виде системы (1.5):

Отсюда последовательно находим

При вычислениях применяется обычный контроль с помощью сумм, причем при составлении суммы учитываются все коэффициенты соответствующей строки.

Заметим, что при действительных a_ij могут получиться чисто мнимые t_ij . Метод применим и в этом случае.

Для изучения данного метода было выбрано программное обеспечение: Matlab 6.5, в операционной системе WindowsXPProfessional. На этапе проектирования была создана программа Square (‘квадрат’). Входными переменными для данной программы является матрица A и соответствующая ей матрица B. Результатом выполнения данной программы является матрица X (выходная переменная), которая является решением системы линейных алгебраических уравнений.

Ниже описан алгоритм реализации метода квадратных корней на языке программирования в среде Matlab 6.5:

A=input(‘Введите матрицу A=’);

if i * — b (x * — полученное решение). Для этого рассмотрим разного рода матрицы:

— влияние мерности матрицы А;

Рассмотрим матрицы мерности 2´2, 3´3, 4´4 и 5´5. Зададим матрицу мерностью 2´2:

, ей соответственно зададим , в результате выполнения программы получим решение:

X =

ε =

Зададим матрицу размерностью 3´3:

, ей соответственно зададим , в результате выполнения программы получим решение:

X =

ε =

Зададим матрицу размерностью 4´4:

, ей соответственно зададим , в результате выполнения программы получим решение:

X =

ε =

Зададим матрицу размерностью 5´5:

, ей соответственно зададим , в результате выполнения программы получим решение:

X =

ε =

Сравним полученные результаты, для этого проанализируем точность полученного решения. Результат мы можем оценить двумя способами и , где E – матрица, полученная в результате подстановки найденного решения в систему линейных алгебраических уравнений: Е=A*x-b. Проиллюстрируем результаты графически. Для этого была разработана программа в среде Matlab 6.5.

МЕТОД РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ.

Метод квадратных корней.

Метод квадратных корней используется для решения линейной системы:

У которой матрица А симметрическая, т.е.

Он является более экономным и удобным по сравнению с методами решения систем общего вида, рассмотренными ранее.

Решение системы осуществляется в два этапа.

Прямой ход. Представим матрицу А в виде произведения двух взаимно транспонированных треугольных матриц:

Перемножая матрицы Т’ и Т и приравнивая матрице A, получим следующие формулы для определения

После того, как матрица Т найдена, систему заменяем двумя эквивалентными ей системами с треугольными матрицами:

Обратный ход. Записываем в развернутом виде системы:

Отсюда последовательно находим:

При вычислениях применяется обычный контроль с помощью сумм, причем при составлении суммы учитываются все коэффициенты соответствующей строки.

Заметим, что при действительных могут получиться чисто мнимые . Метод применим и в этом случае .

Метод квадратных корней дает большой выигрыш во времени по сравнению с рассмотренными ранее методами, так как, во-первых, существенно уменьшает число умножений и делений (почти в два раза для больших n), во-вторых, позволяет накапливать сумму произведений без записи промежуточных результатов.

Задание. Решить систему линейных уравнений методом квадратных корней.

Провести эту работу в SMathStudio.

Схема Халецкого.

Рассмотрим систему линейных уравнений, записанную в матричном виде:

Где — квадратная матрица (i, j = 1, 2, . , n) и

Представим матрицу А в виде произведения А=ВС, где

Тогда элементы будут определяться по формулам

Отсюда искомый вектор х может быть вычислен из цепи уравнений

Так как матрицы B и С треугольные, то системы легко решаются, а именно:

Из формул видно, что числа выгодно вычислять вместе с коэффициентами Эта схема вычислений называется схемой Халецкого. В схеме применяется обычный контроль с помощью сумм.

Схема Халецкого удобна для работы на клавишных вычислительных машинах, так как в этом случае операции «накопления» можно проводить без записи промежуточных результатов.

Задание. Решить систему линейных уравнений методом Халецкого.

Провести эту работу в SMathStudio.

Метод простой итерации

Пусть система линейных уравнений

Каким-либо образом приведена к виду

где С – некоторая матрица, а f – вектор-столбец.

Исходя из произвольного вектора ,

сторим итерационный процесс

или в развернутой форме

Производя итерации, получим последовательность векторов

Доказано, что если элементы матрицы С удовлетворяют одному из условий

то процесс итерации сходится к точному решению системы х при любом начальном векторе , т.е.

Таким образом, точное решение системы получается лишь в результате бесконечного процесса и всякий вектор из полученной последовательности является приближенным решением. Оценка погрешности этого приближенного решения дается одной из следующих формул:

Эти оценки можно усилить соответственно так:

Процесс итераций заканчивают, когда указанные оценки свидетельствуют о достижении заданной точности.

Начальный вектор может быть выбран, вообще говоря, произвольно. Иногда берут Однако наиболее целесообразно в качестве компонент вектора взять приближенные значения неизвестных, полученные грубой прикидкой.

Первый способ. Если диагональные элементы матрицы А отлины от нуля, т. е.

то систему можно записать в виде:

В этом случае элементы матрицы С определяются следующим образом:

и тогда условия приобретают вид:

Неравенства будут выполнены, если диагональные элементы матрицы А удовлетворяют условию:

т.е. если модули диагональных коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов (не считая свободных членов).

Второй способ покажем на примере.

Вообще говоря, для любой системы с невырожденной матрицей существуют сходящиеся итерационные методы решения, но далеко не всегда они удобны для практических вычислений.

Если метод итераций сходится, он дает следующие преимущества по сравнению с методами, рассмотренными выше.

1) Если итерации сходятся достаточно быстро, т. е. если для решения системы требуется менее n итераций, то получаем выигрыш во времени, так как число арифметических действий, необходимых для одной итерации, пропорционально n 2 , а общее число арифметических действий в методе Гаусса, например, пропорционально n 3 .

2) Погрешности округления в методе итераций сказываются значительно меньше, чем в методе Гаусса. Кроме того, метод итераций является самоисправляющимся, т. е. отдельная ошибка, допущенная в вычислениях, не отражается на окончательном результате, так как ошибочное приближение можно рассматривать как новый начальный вектор.

Последнее обстоятельство часто используется для уточнения значений неизвестных, полученных методом Гаусса.

3) Метод итераций становится особенно выгодным при решении систем, у которых значительное число коэффициентов равно нулю. Такие системы появляются, например, при решении уравнений в частных производных.

4) Процесс итераций приводит к выполнению однообразных операций и сравнительно легко программируется на ЭВМ.

Задание. Решить систему линейных уравнений методом простых итераций.

Провести эту работу в SMathStudio.

Метод Зейделя.

Метод Зейделя является модификацией метода простой итерации. Он заключается в том, что при вычислении (k + 1)-го приближения неизвестного x_i при i>1 используются уже вычисленные ранее (k + 1)-е приближения неизвестных Таким образом, для системы вычисления по методу Зейделя ведутся по формулам:

Указанные в методе простой итерации условия сходимости остаются верными и для метода Зейделя. Обычно метод Зейделя дает лучшую сходимость, чем метод простой терации, хотя это бывает не всегда. Кроме того, метод Зейделя может оказаться более удобным при программировании, так как при вычислении нет необходимости хранить значения

Задание. Решить систему линейных уравнений методом Зейделя.