- •Часть 1
- •Оглавление
- •Введение
- •1. Источники и причины погрешностей математической модели
- •Погрешность математической модели
- •Погрешность исходных данных
- •Погрешность численного метода
- •Погрешность проведения расчетов на вычислительных машинах
- •Погрешности округления чисел в эвм
- •Погрешность результатов вычисления арифметических операций
- •“Потеря порядка” и “переполнение” при проведении вычислений на эвм
- •Машинная реализация вычислений
- •Контрольные вопросы и задания
- •2. Системы линейных алгебраических уравнений
- •Прямые методы решения
- •Метод Гаусса
- •Определение числа операций алгоритма метода Гаусса
- •Вычисление определителя матрицы
- •Построение обратной матрицы
- •Метод квадратного корня
- •Определение числа операций алгоритма метода квадратного корня
- •Устойчивость системы линейных алгебраических уравнений
- •Итерационные методы решения
- •Метод Якоби1
- •Метод Зейделя1
- •Сходимость итерационных методов
- •Скорость сходимости
- •Полиномы Чебышёва1
- •Итерационный метод с чебышёвским набором параметров
- •Неявный метод с чебышёвским набором параметров
- •Метод минимальных невязок
- •Метод минимальных поправок
- •Метод скорейшего спуска
- •Неявный метод скорейшего спуска
- •Контрольные вопросы и задания
- •3.НелинейныЕ уравнения
- •Методы вычисления корней нелинейного уравнения1 Метод половинного деления2
- •Метод простых итераций
- •Метод Ньютона2
- •Модификации метода Ньютона
- •Системы нелинейных уравнений
- •Метод простых итераций
- •Метод релаксации
- •Метод Ньютона
- •Нелинейный вариант метода Якоби
- •Нелинейный вариант метода Зейделя
- •Контрольные вопросы и задания
- •Интерполяция степенными функциями
- •Интерполяционный многочлен Ньютона
- •Интерполяционная формула Лагранжа
- •Погрешность полинома Ньютона (Лагранжа)
- •Сходимость интерполяционного процесса
- •Интерполяционный многочлен Эрмита1
- •Интерполяция сплайнами
- •Построение кубического сплайна
- •Сходимость процесса интерполяции кубическими сплайнами
- •Наилучшее приближение в гильбертовом пространстве
- •Метод наименьших квадратов
- •Контрольные вопросы и задания
- •5. Алгебраическая проблема собственных значений
- •Устойчивость собственных значений и векторов
- •Определение собственных значений и векторов Метод интерполяции
- •Трехдиагональные матрицы
- •Поиск собственных векторов
- •Частичная проблема собственных значений
- •Метод линеаризации
- •Степенной метод
- •Метод обратных итераций
- •Контрольные вопросы и задания
- •6.Численное дифференцирование Конечно-разностная аппроксимация
- •Применение интерполяционных формул
- •Контрольные вопросы и задания
- •7.Численное интегрирование
- •Формула прямоугольников
- •Формула трапеций
- •Формула Симпсона1
- •Формула Эйлера1
- •Оценка погрешности методом Рунге2
Сходимость итерационных методов
Сравнивая формулы (2.10) метода Якоби и (2.12) метода Зейделя, можно заметить, что если методы сходятся, то есть в некотором смысле , то они сходятся к решению исходных задач .
Пример 2.5. Рассмотрим еще одну систему алгебраических уравнений, несколько отличающуюся от приведенных в предыдущих примерах:
Точное решение этой системы x = 0,5, y = 1,5 .
Для решения воспользуемся методом Зейделя. Как и ранее, представим уравнения в виде итерационной схемы
Результаты расчетов сведены в табл. 2.3. На рис. 2.3 отражен ход выполнения процедуры Зейделя.
Таблица 2.3
Результаты выполнения итерационной процедуры метода Зейделя
-
n
x(n)
y(n)
0
0,0
1
1,25
4,5
2
-1,0
-4,5
3
3,5
13,5
4
-5,5
-22,5
5
12,5
49,5
6
...
Результаты расчетов показывают, что в последнем случае отсутствует сходимость последовательности результатов к точному решению. Это приводит к необходимости определения условий сходимости той или иной итерационной процедуры.
В общем случае итерационные методы решения систем линейных алгебраических уравнений можно записать в канонической форме
, (2.13)
где - итерационные параметры.
Y -20x + 5y = -2.5
5
4
3
2
1
X
-5 -4 -3 -2 -1 1 2 3 4 5
-1 4x + 2y = 5
-2
-3
-4
-5
Рис. 2.3. Отсутствия сходимости при использовании метода Зейделя
В случае, если не зависят от номера итерации, метод называется стационарным. В частности, для метода Якоби ; для метода Зейделя .
Если , метод называется явным; в случае - неявным.Примеры итерационных методов:
- явный стационарный метод простых итераций
;
- неявный стационарный метод верхней релаксации
.
Введем пространство m - мерных векторов со скалярным произведением
и нормой
.
Определим матричное неравенство: квадратная матрица C > 0 тогда и только тогда, когда
.
Иначе это определение может быть записано следующим образом:
.
Чтобы определить величину , рассмотрим два случая:
1. Пусть симметричная матрица С > 0, тогда согласно первоначальному определению квадратичная форма1 (Сx,x) > 0 . Но квадратичную форму можно привести к каноническому виду в главных осях:
,
где - собственные числа матрицы С; - главные координаты.
В силу С > 0 имеем , вследствие чего , и отсюда получаем
,
то есть в качестве может быть взято наименьшее собственное значение матрицы С.
2. Если С - несимметричная матрица, поступают следующим образом для определения :
,
.
В последнем соотношении индексы суммирования можно поменять местами:
Теперь очевидно, что . Поскольку , то и .
Построим матрицу :
,
но это означает, что построенная матрица является симметричной. Кроме того,
в силу предыдущих соотношений.
Это, в свою очередь, означает, что - наименьшее собственное значение матрицы . Следовательно,
,
то есть указанное выше дополнительное определение положительности имеет место и для несимметричной матрицы.
Оценка
позволяет утверждать, что существует обратная матрица , так как в случае положительной определенности матрицы все ее главные (угловые) миноры положительны (критерий Cильвестра1, [7]).
Для установления условий сходимости определим величину погрешности метода формулой , тогда из формулы (2.13) для стационарного итерационного метода можно получить
,
(2.14)
Теорема 2.4. Пусть А - симметричная положительно определенная матрица, A > 0; итерационные параметры удовлетворяют соотношению
.
Тогда стационарный итерационный метод сходится.
Доказательство. Для доказательства теоремы следует показать, что погрешность метода при любой начальной погрешности .
Построим числовую последовательность вида .
Из формулы (2.14) следует
Теперь можно подсчитать
Вследствие симметрии матрицы А имеем
Иначе говоря, . Отсюда получаем
.
В силу условия теоремы , откуда следует, что , то есть построенная последовательность является монотонно убывающей и, кроме того, в силу , ограничена снизу. Отсюда следует, что существует предел этой последовательности .
Из положительной определенности (B - 0,5A) > 0 следует существование константы >0 такой, что имеет место
.
Теперь предыдущее соотношение может быть переписано в форме неравенства:
.
При n из последнего выражения получаем . Очевидно, что неравенство может выполняться лишь при условии, что .
С другой стороны, , причем существует в силу положительной определенности матрицы А по условию теоремы. Оценим норму погрешности:
.
Теперь становится очевидным, что вследствие имеет место , что и требовалось доказать.
Следствие 1. Пусть А - симметричная положительно определенная матрица. Тогда метод верхней релаксации
сходится при 0 < < 2. В частности, метод Зейделя ( = 1) сходится.
В рассматриваемом случае, очевидно, .
.
Последнее соотношение справедливо в силу симметрии матрицы А:
.
Условие сходимости итерационного метода теоремы 2.4 принимает вид:
Очевидно, что последнее неравенство выполняется при условии .
Следствие 2. Пусть А - симметричная положительно определенная матрица с диагональным преобладанием, то есть имеет место
.
Тогда метод Якоби сходится.
Поскольку в рассматриваемом случае B = D, условие сходимости принимает вид неравенства
.
Из неравенств
,
следует
.
В силу симметричности и положительной определенности матрицы А имеем
.
Используя предположение следствия, запишем
.
Из двух последних неравенств получаем
,
что и требовалось доказать.