- •3 Курса
- •Предисловие
- •Введение
- •Глава 1. Погрешности результата численного решения
- •1.1. Источники ошибок при вычислениях на эвм.
- •1.2. Практическое вычисление функций.
- •1.3. Схема Горнера и метод Ньютона
- •В общем виде алгоритм запишется:
- •1.5. Метод простых итераций.
- •1.6. Метод деления отрезка пополам (метод дихотомии).
- •1.7. Метод хорд.
- •Программа метода дихотомии.
- •Программа метода простых итераций.
- •Программа метода Бэрстоу.
- •Программа метода хорд.
- •Программа метода секущих.
- •Глава 2 Решение систем линейных уравнений
- •2.1. Метод Гаусса.
- •2.2. Метод итераций (Гаусса-Зейделя).
- •2.4. Стандартные операторы мatlab для решения систем линейных алгебраических уравнений.
- •2.5. Решение систем нелинейных уравнений.
2.2. Метод итераций (Гаусса-Зейделя).
Рассмотрим метод на примере системы (2.2), преобразовав ее к виду:
(2. 5)
Если задать начальные приближения , то получим из первого уравнения первое приближение . Подставим его и во второе уравнение получим . Подстав в третье уравнение и получим , т.е.:
Аналогичным образом можно продолжить итерации и поэтому можно записать алгоритм в общем виде:
(2.6)
Процесс итераций следует продолжать до удовлетворения неравенств max . Строго говоря, это не метод простых итераций, поскольку вновь полученные значения используются далее на той же итерации. Метод итераций предпочтительнее, если число итераций менее n. Число операций для метода итераций пропорционально n2 , а для метода Гаусса оно пропорционально n3.
Метод итераций позволяет наглядно показать графически роль ведущих элементов расположенных на главной диагонали.
рис. 2.2
Рассмотрим систему Запишем ее в форме (2.6):
Выбираем точку на прямой (a) y=0 и x=1. Определяем значение y на прямой (b) y = 3/2. Вновь переходим на прямую (a) и определяем x = 1/4 , переходим на прямую (b) и определяем y=9/8. На рис. 2.2 видим, что процесс итераций сходится к решению системы x =2/5 , y = 6/5. Переставим уравнения, т.е. запишем .
Для начального значения y = 0 имеем на прямой (c) x = -2.
Переходим на прямую (d) и определяем y = 6. И далее необходимо перейти на прямую (c) и т.д. Очевидно, что процесс итераций расходится. Сравните диагональные элементы для систем (a), (b) и (c), (d).
Имеются жесткие необходимые условия, которые обеспечивают сходимость метода:
В каждой строке диагональный элемент превосходит сумму всех остальных. Такие матрицы называются строго диагонально доминирующими.
Во многих прикладных областях техники при решении уравнений в частных производных возникает необходимость решать системы линейных уравнений итерационными методами, которые к счастью удовлетворяют требованиям сходимости.
2.3. Метод LU преобразования.
Разложим матрицу A на произведение нижней треугольной матрицы L c единицами на главной диагонали и верхней треугольной U с неравными нулю диагональными элементами. Тогда система уравнений запишется: LUx = b.
Верхняя треугольная матрица получается методом исключения Гаусса. А нижняя треугольная содержит в качестве элементов множители, использованные для исключения Гаусса. Треугольные системы легко решать.
Например,
Поскольку предполагается, что A не вырождена, то диагональные элементы для всех k.
Кроме того, требуется вводить в разложение матрицу перестановок P: PA = LU. Это эквивалентно перестановке строк при выборе главного элемента. Например, .
Для примера, рассмотренного в методе Гаусса, приведем представление матрицы в виде:
А=РLU, т.е. разложим матрицу А в произведение PLU, где Р – матрица перестановок, а L и U – треугольные матрицы (нижняя и верхняя).
Р – единичная матрица, но с учётом перестановок строк при выборе главного диагонального элемента.
U – верхняя треугольные матрица для обратного хода метода Гаусса.
L – нижняя треугольная матрица, в диагонали которой расположены 1, а множители mi используются в качестве элементов.
, , ,
Представление А=PLU называется LU – разложением или треугольным разложением матрицы А.
Треугольное разложение можно сформировать не зная матрицы b , а это весьма удобно для решения задач, в которых при одной и той же матрице А необходимо решить систему Ax=b для различных матриц b.
После разложения решение исходной системы можно найти, решая более простые системы:
Pz=b, , ( ), (2.7)
Ly=z, , ( ), (2.8)
Ux=y, , ( ). (2.9)
Подставляя последовательно y из уравнения (2.9) в уравнение (2.8), а затем z из уравнения (2.8) в уравнение (2.7), получим исходную систему PLUx=b.
Имея в распоряжении матрицы P, L и U, необходимо получить решения, записанные в формулах (2.7), (2.8) и (2.9).