Численные методы решения СЛАУ

Размещено на http://www.allbest.ru/

Лекционный курс

Тема: Численные методы решения СЛАУ (5 часов)

План

1. Методы решения систем линейных уравнений

2. Конечные методы решения систем линейных уравнений

3. Итерационные методы решения систем линейных уравнений

Литература

1. Методы решения систем линейных уравнений

Системой Линейных Алгебраических Уравнений (СЛАУ) будем называть систему уравнений следующего вида:

A11

*X1

+

A12

*X2

+

A13

*X3

+

A14

*X4

+

…

+

A1n

*Xn

=

B1

A21

*X1

+

A22

*X2

+

A23

*X3

+

A24

*X4

+

…

+

A2n

*Xn

=

B2

….

…

…

…

…

…

…

.

…

….

….

.

…

An1

*X1

+

An2

*X2

+

An3

*X3

+

An4

*X4

+

…

+

Ann

*Xn

=

Bn

Такую систему уравнений можно записывать в сокращенном виде, используя как минимум 2 формы:

С использованием знака суммы

С использованием матриц: А*Х=В, здесь А - матрица системы, Х - вектор неизвестных, В - вектор правой части. Иногда используют расширенную матрицу системы А' - которая образуется дописыванием вектора В справа к матрице А.

Матрица системы:

A11	A12	A13	A14	…	A1n
A21	A22	A23	A24	…	A2n
….	….	….	….	….	….
An1	An2	An3	An4	…	Ann

Расширенная матрица системы:

A11	A12	A13	A14	…	A1n	B1
A21	A22	A23	A24	…	A2n	B2
….	….	….	….	….	….	….
An1	An2	An3	An4	…	Ann	Bn

В алгебре для линейных уравнений вводится понятие линейной зависимости.

О. Линейной комбинацией уравнений Т и М называют уравнение полученное по формуле

С1*Т+ С2*М,

где С1 и С2 постоянные коэффициенты.

Если одно из уравнений системы может быть представлено линейной комбинацией остальных, то такая система называется линейно-зависимой. Линейная зависимость системы определяется вырождением матрицы системы.

О. Матрица А будет вырожденной, если определитель этой матрицы равен нулю => det(A)=0.

Линейная зависимость СЛАУ означает, что некоторые из уравнений системы «лишние» и могут быть без ущерба для решения удалены из системы. В дальнейшем будем считать, что все зависимые уравнения уже удалены из системы, хотя проверку неравенства нулю определителя матрицы системы будем планировать перед решением СЛАУ.

В алгебре доказывается, что для линейно независимой СЛАУ, в которой N уравнений и M неизвестных:

При N>M (число уравнений больше числа неизвестных) - решения СЛАУ не существует.

При N<M (число уравнений меньше числа неизвестных) - существует бесконечно много решений СЛАУ.

При N=M (число уравнений равно числу неизвестных) - существует единственное решение СЛАУ.

Нас интересует только последний вариант, поэтому будем считать, что число уравнений равно числу неизвестных. Таким образом, рассмотрим методы численного решения СЛАУ с квадратной матрицей системы, которая является линейно-независимой. Для численного решения СЛАУ (аналогично нелинейных уравнениям) используют конечные и итерационные методы.

2. Конечные методы решения систем линейных уравнений

В конечном методе можно заранее точно указать количество операций, которое потребуется для решения СЛАУ.

Метод исключения Гаусса

Метод делится на два этапа: прямой и обратный ход. Прямой ход - с помощью эквивалентных преобразований (не изменяющих решения системы) исключаем элементы (делаем равными 0), лежащие ниже или выше главной диагонали. В общем случае необходимо получить треугольную матрицу. Тогда возможны 2 варианта: приведение матрицы системы к L или U виду.

О. Главной диагональю квадратной матрицы называют множество элементов с одинаковыми индексами Aii. Эти элементы располагаются на диагонали матрицы от верхнего левого угла до правого нижнего.

О. Матрица называется треугольной, если все элементы, лежащие ниже главной диагонали равны нулю (L -матрица, от слова Low-нижний) или выше главной диагонали равны нулю (U -матрица, от слова Upper-верхний)

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

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

Деление или умножение строки на любое постоянное число, кроме 0.

Сложение или вычитание любых двух строк.

Построение линейных комбинаций строк.

Перестановка строк.

Перестановка столбцов с одновременным изменением индексов переменных.

Рассмотрим процесс исключения прямого хода на примере получения L матрицы:

a11	a12	a13	a14	…	a1n	b1
a21	a22	a23	a24	…	a2n	b2
….	….	….	….	….	….	….
an1	an2	an3	an4	…	ann	bn

В данном случае необходимо исключить элементы, лежащие ниже главной диагонали. При исключении элемент нужно будет обратить в ноль. Исключения производятся по столбцам, при этом базовым или главным является диагональный элемент и его строка. Для L матрицы нужно начинать с 1-го столбца и исключать элементы ниже главной диагонали. Таким образом, номер столбца будет совпадать с номером главной строки, которая содержит главный диагональный элемент. Легко убедиться, что вариант исключения, приводящий к получению L матрицы из произвольной матрицы можно реализовать с помощью линейных преобразований следующего вида:

=> => и

Для получения U - матрицы необходимо идти в обратную сторону:

Точность вычисления по методу Гаусса определяется процессами округления при этом, чем больше абсолютное значение использующегося диагонального элемента, тем точнее будет вычисление. Если диагональный элемент =0, то вычислять нельзя. Если он мал, то результат будет неточным.

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

Таким образом, метод Гаусса существует в двух видах: просто метод Гаусса и с выбором главного элемента.

Рассмотрим обратный ход метода Гаусса. Пусть в результате исключения мы получим L матрицу.

=> => =>

получили формулу обратного кода для L матрицы при

Для U - матрицы:

Метод полного исключения Жордана

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

Для такого исключения можно воспользоваться той же формулой Гаусса, но индексы меняются иначе:

m =1,2…n. j = 1…n

Обратный ход для метода Жордана чрезвычайно прост.

i = 1,2…n.

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

Использования метода Гаусса и Жордана для матричных вычислений

Вычисление определителя матрицы.

Так как исключения в методе Гаусса не меняют значение определителя матрицы, то с помощью прямого хода можно привести матрицу к треугольному виду L или U. В тоже время определитель треугольной матрицы равен произведению диагональных элементов. Следовательно, получаем алгоритм вычисления определителя для произвольной матрицы:

По данной формуле производим исключение элементов выше или ниже главной диагонали и перемножаем элементы главной диагонали

Определение элементов обратной матрицы:

По определению обратной матрицы . Это произведение эквивалентно множеству систем уравнений для столбцов обратной матрицы. Таким образом, определение обратной матрицы сводится к решению систем линейных уравнений, где вектор неизвестных - один из столбцов обратной матрицы, а в правой части один из столбцов единичной матрицы. Матрица системы во всех уравнениях ода и та же. Для решения этих систем лучше использовать метод Жордана.

Метод Халецкого

Суть метода Халецкого в разложении матричной системы в произведение матрицы U*L = A. При этом диагональные элементы одной из треугольных матриц равны 1. Для решения методом Халецкого необходимо получить матрицы разложения и воспользоваться обратным ходом:

=> => =>

В методе Халецкого вместо 1 задачи решения СЛАУ получают 2 задачи решения СЛАУ, но обе эти задачи имеют треугольные матрицы систем и решаются только с помощью 2-х обратных хода. Поскольку обратный ход имеет только 2 цикла вместо 3 циклов прямого хода, то такой вариант сулит значительные выгоды. Все определяется только затратами на

Для решения полученной системы уравнений требуется следующие формулы обратного хода для треугольных матриц U и L:

Для U - матрицы:

,

для L матрицы

Очень интересен алгоритм вычисления элементов матриц разложения L и U. Диагональные элементы матрицы Ukk =1. Воспользуемся формулой произведения матриц. A=U*L =Aij= - здесь строка U умножается на столбец L. 1-я строка U и 1-й столбец L содержат только по одному элементу => A11=L11, далее можно найти элементы 2-й строки U и 2 столбца L => 3-я строка и 3-й столбец и т.д.. Таким образом, вычисление треугольных матриц максимально оптимизировано. Кроме того, элементы этих матриц можно последовательно располагать на месте элементов матрицы A. Когда размер оперативной памяти - критичный параметр, такой алгоритм будет очень полезным.

Сравнительная характеристика методов решения СЛАУ

При решении сравнительно небольших СЛАУ метод Гаусса выгоднее других методов компромиссом между простотой и скоростью. Метод Жордана проще чем метод Гаусса, но требует гораздо больше вычислений (так как использует двойной прямой ход). Метод Халецкого быстрее метода Гаусса, но при этом и гораздо сложнее для реализации.

Сравнение вариантов метода Гаусса с выбором главного элемента и без него показывает, что выбор главного элемента всегда лучше.

При увеличении размера СЛАУ метод Гаусса постепенно теряет свое преимущество перед методом Халецкого. Этот метод разработан специально для ЭВМ и имеет оптимальные варианты расчета.

Метод Жордана особенно удобен при решении задач, когда есть много СЛАУ у которых одна матрица (например при вычислении обратной матрицы). В такой задаче он существенно лучше метода Гаусса. Правда в этой задаче ему конкурентом является метод Халецкого, где так же можно оптимизировать подобные вычисления.

3. Итерационные методы решения систем линейных уравнений

В алгебре для векторов и матриц вводят численную характеристику - норму. В некоторых случаях она имеет аналогию с длиной. Норма должна удовлетворять условиям:

Обычно определяют 3 разных нормы:

а)

в) бесконечная

с) Евклидова

Итерационные методы СЛАУ основаны на получении итерационных векторов последовательных приближений. Находится каждое к-е приближение через к-1:

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

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

Пусть задана система уравнений которая записывается в виде

.

Выразим из этой системы в каждом уравнении по одной неизвестной

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

Теорема: Если матрица А не вырождена и норма преобразованной матрицы , то метод простой итерации будет сходящимся.

Замечание:

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

Таким образом, либо

=>

Рассмотрим формулу для

, =

Для всех строк i: - условие диагонального преобладания. Модуль элемента главной диагонали больше суммы модулей остальных элементов строки. Такое условие должно быть справедливо для всех строк. Из второй нормы получаем другое условие . В данном случае диагональный элемент должен быть больше по модулю суммы модулей остальных элементов столбца. Это свойство справедливо для всех столбцов.

Алгоритм метода простой итерации

Выбираем и преобразуем матричную систему к итерационному виду .

Используя итерационную формулу находим следующее приближение.

Сравним по формуле норму с заданной погрешностью. Если условие выполняется, то прекращаем вычисление, в противном случае, возвращаемся к n 2.

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

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

- формула Зейделя.

У Зейделя каждое приближение сходится быстрее, чем в методе простой итерации. Поэтому весь метод сходится гораздо быстрее. Сходимость метода Зейделя можно определять по формулам метода простой итерации (так как этот метод просто улучшение метода простой итерации => если сходится простой метод, то должен сходиться и улучшенный метод).

Метод координатной релаксации

Суть метода - последовательное уменьшение (релаксации) вектора невязки.

Пусть задана система уравнений A*X=B, если у нас есть некое приближение к точному решению X(0), то после подстановки этого приближения в систему уравнений равенства не будет A* X(0)B => можно определить вектор разности правой и левой части N= B -A* X(0) - это вектор невязки. Чем точнее приближение, тем меньше вектор невязки (в общем случае норма вектора невязки стремится к нулю при приближении к точному решению). Таким образом, если есть метод, который будет последовательно уменьшать вектор невязки, то этот метод является методом решения СЛАУ. Такой метод назвали методом релаксации. Построим алгоритм подобного метода путем изменения на 1 шаге только 1 координаты, когда это изменение приводит к обнулению максимального по модулю элемента вектора невязки. Примерный алгоритм:

Задаем систему уравнений (все исходные матрицы A и B).

Выбираем начальное приближение X(0) = B аналогично методу простой итерации (в методе релаксации сходимость тоже не зависит от выбора начального приближения).

Вычислим вектор невязки по формуле

Найдем максимальный по модулю элемент вектора невязки Nk = maxi(Ni) здесь k - номер максимального элемента.

Изменим xk на такую величину xk, чтобы

Nk = 0. => => => .

Данная формула дает простое вычисление xk.

Теперь вычислим следующее приближение

Х(t)p = Х(t-1)p при pk и Х(t)k = Х(t-1)k+xk

и следующее приближение вектора невязки

.

Эти формулы являются итерационными формулами для данного метода.

Повторяем п.4-6 до тех пор пока норма вектора невязки не станет меньше заданной погрешности ||N||< - это условие прерывания итераций в данном итерационном методе.

Сравнительная характеристика итерационных методов решения СЛАУ

Наиболее быстрый метод Зейделя, но он и самый сложный по формуле вычисления. Однако для большинства задач это усложнение вычисления не очень важно.

Метод релаксации наименее сходящийся и количество итераций в нем всегда гораздо больше чем в других методах, но зато и операций на 1 итерацию здесь в N (число уравнений) раз меньше. Поэтому эффективность метода возрастает при увеличении числа уравнений в СЛАУ.

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

Кроме рассмотренных выше, в данном курсе будет изучаться особый метод решения СЛАУ - метод прогонки. При этом он решает СЛАУ особого вида и будет рассмотрен позже.

алгебраический уравнение гаусс матрица

Литература

1. Бахвалов Н. и др. Численные методы. - М.: Лаборатория базовых знаний. 2000.-624с.

2. Бахвалов Н.С. и др. Численные методы в задачах и упражнениях. -М.:Высшая школа.2000. -190с.

3. Вержбицкий В.М. Численные методы. Математический анализ и ОДУ.-М.: Высшая школа. 2001. -382 с.

4. Вержбицкий В.М. Численные методы. Линейная алгебра и нелинейные уравнения.-М.: Высшая школа. 2000. -266 с.

5. Гриненко Е.В., Емельянова М.В., Пушечкин Н.П. Численные методы (учебно-методическое пособие).- Славянск-на-Кубани. ч.1 ООО «Берегиня». 2003. -64 с. ч.2 Изд. СГПИ. 2005. -56 с.

Размещено на Allbest.ru

...