- •Список принятых сокращений
- •Тема 1. Методы решения систем линейных уравнений
- •Лекция 1. Метод Гаусса
- •Концепция методов
- •Метод Гаусса
- •Верхняя треугольная система линейных уравнений
- •Метод исключения Гаусса и выбор главного элемента
- •Схема единственного деления
- •Лекция 2. Итерационные методы
- •Метод итераций
- •Замечания о точности расчета
- •Достаточное условие
- •Приведение линейной системы к виду удобному для итерации.
- •Метод Зейделя
- •Тема 2. Методы решения нелинейных уравнений
- •Лекция 3. Метод половинного деления
- •Приближенное решение нелинейных уравнений
- •Отделение корней
- •Метод половинного деления
- •Лекция 4. Метод Ньютона
- •Методика решения задачи
- •Ошибка деления на нуль.
- •Скорость сходимости.
- •Модификации метода Ньютона.
- •Упрощенный метод Ньютона
- •Метод Ньютона-Бройдена
- •Метод секущих
- •Тема 3. Численное интегрирование
- •Лекция 5. Метод трапеций
- •Постановка задачи
- •Формула трапеций
- •Погрешность формулы трапеций
- •Общая формула трапеций
- •Лекция 6. Метод Симпсона
- •Формула Симпсона
- •Остаточный член формулы Симпсона
- •Общая (обобщенная) формула Симпсона
- •Тема 4. Обработка экспериментальных данных
- •Лекция 7. Интерполирование
- •Постановка задачи
- •Линейная интерполяция
- •Квадратичная интерполяция
- •Интерполяционная формула Лагранжа.
- •Вычисление Лагранжевых коэффициентов
- •Интерполяция сплайном
- •Лекция 8. Метод наименьших квадратов
- •Постановка задачи
- •Метод наименьших квадратов
- •Линейная аппроксимация (интерполяция)
- •Коэффициент линейной корреляции
- •Квадратичная аппроксимация
- •Приложения
- •Транспонирование
- •Вычисление определителя матрицы
- •Нахождение обратной матрицы
- •Сложение и вычитание матриц
- •Умножение матрицы на число
- •Умножение матриц
- •Итерационные методы решения уравнений
- •Стандартные формы уравнений
- •Поиск корней графическим методом
- •Простой итерационный метод догадки и проверки
- •Представление уравнения в форме 2
- •Прямая подстановка
- •Итерации в ячейке
- •Введение в надстройку Поиск решения
- •Активирование надстройки Поиск решения
- •Установка надстройки Поиск решения
- •Применение надстройки Поиск решения
- •Приложение 3. Контрольные вопросы
- •Приложение 4. Список лабораторных работ
- •Часть 1. Вычислительная техника
- •Часть 2. Численные методы
- •Список литературы.
- •Основная литература
- •Дополнительная литература
- •Интернет-ресурсы
Лекция 2. Итерационные методы
При большом числе неизвестных линейной системы схема метода Гаусса, дающая точное решение, становится весьма сложной. В этом случае целесообразнее использовать приближенные (итерационные) численные методы решения систем линейных уравнений. Рассмотрим два из таких методов – метод итераций и метод Зейделя.
Метод итераций
Пусть дана система уравнений:
a |
11 |
x |
1 |
+ a |
12 |
x |
2 |
+ ...+ a |
1n |
x |
n |
= b |
|||||
|
|
|
|
|
|
1 |
|||||||||||
a21 x1 + a22 x2 + ...+ a2n xn = b2 |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
........................................................ |
|||||||||||||||||
a |
n1 |
x |
1 |
+ a |
n2 |
x |
2 |
+ ...+ a |
nn |
x |
n |
= b |
|||||
|
|
|
|
|
|
|
|
|
|
|
n |
Предполагая, что диагональные коэффициенты aii ≠ 0
(2.1)
(i = 1,2,...,n) раз-
решим первое уравнение системы (2.1) относительно x1 , второе – относительно x2 и т.д. Получим эквивалентную систему:
x1 = β1 +α12 x2 +α13 x3 + ...+α1n xn |
|
|
|
= β2 +α21 x1 +α23 x3 + +α2n xn |
|
x2 |
(2.2) |
|
|
|
|
.................................................................. |
|
|
|
= βn +αn1 x1 +αn2 x2 + +αnn−1 xn−1 |
|
xn |
|
|
|
b |
|
aij |
при i ≠ j и αij = 0 при i = j (i , j = 1,2,...,n). |
|
где βi |
= |
i |
, αij |
= − |
|
|
|
aii |
|||||
|
|
aii |
|
|
||
Будем решать систему (2.2) методом последовательных приближений. |
||||||
За |
нулевое |
приближение примем столбец свободных членов |
x(0) = β (β1 ,β2 ,...,βn ). Новое приближение получим, подставляя значения x(0) в систему (11.2). Запишем формулы приближений в развернутом виде:
x(0) |
= β |
|
|
|
|
|
||
|
i |
+ |
|
i |
n |
|
||
|
|
|
|
|
||||
xi(k |
|
1) = βi + ∑αij x(jk ) |
(2.3) |
|||||
|
|
|
|
|
j=1 |
|
||
(αii |
= 0; |
i = 1,...,n; k = 0,1,2,....) |
|
|||||
Таким образом, получим последовательность приближений xi(0) , |
xi(1), xi(2) , |
|||||||
…, xi(n) которая сходится, если |
|
xi(n+1) − xin |
|
< ε . Этот метод называется мето- |
||||
|
|
дом итераций.
Процесс итерации хорошо сходится, т.е. число приближений, необходимых для получения корней системы (2.1) с заданной точностью невелико, если элементы матрицы α малы по абсолютной величине. Иными словами, для ус-
16
пешного применения процесса итерации модули диагональных коэффициентов системы должны быть велики по сравнению с модулями недиагональных коэффициентов этой системы (свободные члены при этом роли не играют).
Пример 1. Решить систему методом итераций:
4 x1 + 0,24 x2 − 0,08 x3 = 8 |
|
||||||
|
x1 |
+ 3 |
x2 − 0,15 |
x3 |
= 9 |
(2.4) |
|
0,09 |
|||||||
|
x1 |
− 0,08 x2 |
+ 4 |
x3 |
= 20 |
|
|
0,04 |
|
||||||
Диагональные коэффициенты |
4; 3; 4 |
системы значительно преобладают |
над остальными коэффициентами при неизвестных. Приведем эту систему к нормальному виду (2.2):
x1 = 2 |
− 0,06 |
x2 + 0,02 x3 |
|
|
|
= 3 − 0,03 |
x1 + 0,05 x3 |
(2.5) |
|
x2 |
||||
|
= 5 |
− 0,01 |
x1 + 0,02 x2 |
|
x3 |
|
|||
За нулевые приближения корней системы (2.4) принимаем: |
||||
x1(0) = 2 ; |
|
x2(0) = 3 ; |
x3(0) = 5 |
Подставляя эти значения в правые части уравнений (2.5), получим первые приближения корней:
x1(1) = 2 − 0,06 3 + 0,02 5 = 1,92x2(1) = 3 − 0,03 2 + 0,05 5 = 3,19x3(1) = 5 − 0,01 2 + 0,02 3 = 5,04
Далее, подставляя эти найденные приближения в формулу (2.5) получим вторые приближения корней:
x1(2) = 1,9094 ; |
x2(2) = 3,1944 ; |
x3(2) = 5,0446 |
Далее выполняем третью подстановку и т.д. Результаты вычислений приведены в таблице 2.1
Таблица 2.1 Вычисление решения системы линейных уравнений методом итераций
k |
x1(k ) |
x2(k ) |
x3(k ) |
0 |
2 |
3 |
5 |
1 |
1,92 |
3,19 |
5,04 |
2 |
1,9094 |
3,1944 |
5,0446 |
3 |
1,90923 |
3,19495 |
5,04485 |
Замечание: При применении метода итераций нет необходимости за нулевое приближение принимать столбец свободных членов. Метод итерации обладает тем свойством, что если он сходится, то сходится при любом начальном приближении. Причем, сходящийся процесс итерации обладает важным свой-
ством самоисправляемости (самокоррекции), т.е. отдельная ошибка в вычис-
17
лениях не отразится на конечном результате, т.к. ошибочное приближение можно рассматривать как новый начальный вектор и процесс как бы начинается снова.
Замечания о точности расчета
Если все коэффициенты и свободные члены системы являются точными числами, то решение ее методом последовательных приближений может быть получено с любым заранее заданным числом m верных десятичных знаков. При этом в значениях последовательных приближений следует удерживать m + 1 десятичных знаков и последовательные приближения вычислять до их совпадения, после чего нужно округлять результат на один знак. Если коэффициенты и свободные члены системы являются приближенными числами, написанными с p знаками, то решение этой системы производится, как в случае
точных чисел, с точностью до m = p знаков.
Достаточное условие
Теорема. Если для приведенной системы (2.2) выполнено хотя бы одно из условий:
|
n |
|
|
|
1) |
∑ |
αij |
< 1 |
(i = 1,2,...,n) |
или |
j=1 |
|
|
|
n |
|
|
||
|
|
|
||
2) |
∑ |
αij |
< 1 |
( j = 1,2,...,n) |
|
i=1 |
|
|
|
то процесс итерации сходится к единственному решению этой системы, независимо от выбора начального приближения.
Следствие. Для системы (2.1) метод итераций сходится, если выполнены неравенства:
|
n |
|
|
aii |
> ∑ |
aij |
(i = 1,2,...,n) |
|
i=1 |
|
|
|
( j≠i ) |
|
т.е. если модули диагональных коэффициентов для каждого уравнения системы больше суммы модулей всех остальных коэффициентов строки (не считая свободных членов).
Приведение линейной системы к виду удобному для итерации.
Система приводится к необходимому виду (удовлетворяющему условию теоремы) следующим образом. Из уравнений системы выбираются такие уравнения, для которых диагональные элементы этих уравнений, поставленных на соответствующее место, были бы больше суммы остальных коэффициентов. Оставшиеся уравнения (которые не удовлетворяют таким требованиям) приводятся к необходимому виду с помощью линейных преобразований. Преобразовываются линейной комбинацией так, чтобы каждое из них образовало одно из недостающих уравнений системы. Покажем данные положения на примере.
Пример 2. Привести систему к виду, годному для применения метода итераций.
18
|
2 x1 + 3 x2 − 4 x3 + x4 = 3 |
|||
|
|
− 2 x2 |
− 5 x3 |
+ x4 = 3 |
x1 |
||||
|
|
|
|
− 4 x4 = 1 |
5 x1 − 3 x2 + x3 |
||||
|
|
x1 + 2 |
x2 − x3 + 2 x4 = −4 |
|
10 |
(A) (Б) (B) (Г)
В уравнении (Б) коэффициент при x3 по модулю больше суммы модулей
остальных коэффициентов, поэтому можно принять это уравнение за третье уравнение в преобразованной системе. Коэффициент при x1 в уравнении (Г)
также больше суммы модулей остальных коэффициентов, поэтому можно принять это уравнение за первое уравнение преобразованной системы. Таким образом, новая система имеет вид:
10 |
x1 + 2 |
x2 − x3 + 2 |
x4 = −4 |
(I ) |
|
|
|
|
(II ) |
........................................ |
|
|
......... |
|
|
− 2 x2 |
− 5 x3 + x4 |
= 3 |
(III ) |
x1 |
||||
|
|
|
|
(IV ) |
........................................ |
|
|
........ |
Анализируя данную систему, можно заметить, что для получения уравнения (II ) с максимальным по модулю коэффициентом при x2 достаточно со-
ставить разность (A)− (Б):
x1 + 5 x2 + x3 + 0 x4 = 1 |
(II ) |
Теперь в новую систему вошли уравнения (A), (Б), (Г), поэтому в урав- |
|
нение (IV ) обязательно должно войти уравнение (B) исходной системы. Под- |
|
бором убеждаемся, что за уравнение (IV ) можно взять линейную комбинацию: |
2 (A)− (Б)+ 2 (В)− (Г), т.е.
3 x1 + 0 x2 + 0 x3 − 9 x4 = 10 |
(IV ) |
||
Таким образом, преобразованная система получена при следующих преоб- |
|||
разованиях: |
|
|
|
(I ) |
|
(Г) |
|
(II ) |
(А)− (Б) |
|
|
(III ) |
|
(В) |
|
(IV ) |
|
2 (A)− (Б)+ 2 (В)− (Г) |
В итоге получим преобразованную систему уравнений, эквивалентную исходной и удовлетворяющую условиям сходимости процесса итераций. Разрешив полученную систему относительно диагональных неизвестных, получим систему
19