§1. Системы линейных уравнений: метод простых итераций, метод Зейделя
Задача: Дано: , i =1,..., m.
Найти: , удовлетворяющее системе.
Пусть система Крамеровская, т.е. m = n.
Запишем систему в матричной форме:
(1),
где – столбец неизвестных, – столбец свободных коэффициентов.
Метод простых итераций:
1. Преобразуем уравнение (1) в уравнение вида (2) (B=E-A);
2. Составим рекуррентную формулу: (3);
3. Выберем любое начальное приближение .
По формуле (3) найдем , , …, ;
4. Если метод сходится, то последнее найденное приближение приблизительно равно решению системы (2).
Определения нормы вектора:
Опр. 1. .
Опр. 2. .
Опр. 3. .
Определения нормы матрицы, согласованной с нормой вектора:
Опр. .
Следовательно:
Опр. 1. .
Опр. 2. .
Опр. 3. , где – собственное значение матрицы , – сопряженная к A матрица (.
Замечание: Если уменьшается при , то метод простых итераций сходится.
Теорема. (Достаточное условие сходимости метода простых итераций)
Если || B || < 1, то система (2) имеет единственное решение, и итерационный процесс по формуле (3) сходится со скоростью убывающей геометрическое прогрессии.
|
|
Док-во:
1. Если – решение системы (2), то
.
Тогда однородная система имеет решение, удовлетворяющее
, т.е. решение существует (нулевой вектор) и единственное.
Следовательно система (2) имеет единственное решение (по теореме об общем решении СЛУ, равной сумме общего решения однородной системы и частного решения неоднородной).
2. Пусть – точное решение системы (2).
Тогда – погрешность на шаге k, и
; при .
Если обозначить , то норма погрешности меньше членов убывающей геометрической прогрессии с шагом q.
Теорема 2. (без док-ва) (Необходимое и достаточное условие сходимости метода простых итераций)
Пусть система (2) имеет единственное решение. Итерационный процесс по формуле (3) сходится к решению системы (2) при любом начальном приближении тогда и только тогда, когда все собственные значения матрицы B по модулю меньше 1.
Своеобразная модификация метода простых итераций – метод Зейделя.
Метод Зейделя:
Пусть в системе (1) в матрице A все диагональные элементы отличны от нуля.
1. Определим матрицы ; .
Получим систему (4).
2. Построим рекуррентную формулу (5).
3. Выберем любое начальное приближение .
Система (5) имеет вид
Из первого уравнения системы (5) найдем , из второго уравнения системы (5) найдем , и т.д. Таким образом, найдем . Аналогично, найдем , …, .
4. Если норма разности уменьшается, то метод сходится, и последнее найденное приближение приблизительно равно решению системы (4).
Замечание: Формула (5) равносильна формуле . Тогда . Итерационный процесс сходится, если все собственные значения матрицы по модулю меньше 1.
|
|
Теорема 3. (без док-ва)
Если A – вещественная, симметричная, положительно определенная (т.е. все главные миноры положительны) матрица, то метод Зейделя сходится.
§2. Метод наискорейшего спуска
Итерационные методы решения СЛУ сводятся к поиску вектора , минимизирующего функцию .
Воспользуемся теорией ФНП из мат.анализа:
– вектор, в направлении которого скорость возрастания наибольшая.
, где – частная производная по переменной l.
Получаем рекуррентную формулу:
(6),
где – некоторый параметр, определяемый из условия:
.
Особый случай.
Пусть A – симметричная и положительно определенная матрица.
Пусть .
Точка минимума такой функции является решением уравнения .
Доказывается подстановкой и по определению – пропускаем.
Тогда .
.
Пусть .
, где – параметр, определяемый из условия:
.
Выведем формулу для нахождения .
Рассмотрим
(т.к. A – симметричная, то
Т.о. – квадратная функция с положительным коэффициентом при .
(т.к. A – положительно определенная, то для любого )
в точкеминимума.
– значение, при котором .
§ 3. Обратная интерполяция для решения нелинейных уравнений
Задача: Дано: f (x) = 0
Найти: x 0, такой, что f (x 0)=0.
Пусть точное решение x T Î [ a, b ] и f (x) обратима на [ a, b ], т.е. существует обратная функция g (x) = f –1(x): g (f (x))= x.
Тогда g (0)= g (f (x T))= x T.
Алгоритм:
1) Выбрать [ a, b ]: f (x) обратима (монотонна).
2) Выбрать узлы x 0,..., x n Î [ a, b ].
Вычислить значения f (x) в узлах: f (x 0),..., f (x n).
3) Для g (x): f (x 0),..., f (x n) — узлы
x 0,..., x n — значения в узлах.
Найти интерполяционный многочлен Ln (x)» g (x).
4) Ln (0)» g (0) = x T — приближенное значение корня уравнения.
§ 4. Системы нелинейных уравнений: метод простых итераций
Задача: Дано: (7),
где – столбец неизвестных, – столбец, состоящий из скалярных функций от n переменных.
Метод простых итераций:
1) Преобразовать уравнение (7) в уравнение вида (8);
2) Составить рекуррентную формулу: (9);
3) Выбрать любое начальное приближение . По формуле (9) найти , , …, ;
4) Если норма разности уменьшается, то метод сходится, и последнее найденное приближение приблизительно равно решению системы (7).
Опр. Метрическое пространство H — множество, на котором задана функция метрики (расстояния) r (a, b), удовлетворяющая условиям:
1) r (a, b) ³ 0, и r (a, b) = 0 Û a = b;
2) r (a, b) = r (b, a);
3) r (a, b) + r (b,c) ³ r (a, c).
В нашем случае H = ú n, .
Опр. Отображением в метрическом пространстве называется функция
g: H ® H.
Опр. Отображение называется сжимающим, если существует число q:
0 ≤ q < 1, такое, что для любых x 1, x 2 Î H выполняется
r (g (x 1), g (x 2)) ≤ q × r (x 1, x 2).
Теорема.
Если отображение является сжимающим, то уравнение имеет единственное решение и .
Док-во:
1. Поскольку является сжимающим, то
(обозначили ).
Тогда для l > k выполняется
Т.о. при l ® ¥, k ® ¥ выполняется , следовательно последовательность , , …, ,… сходится к предельному значению .
2.
.
Это неравенство верно для любого k, т.е. меньше сколь угодно маленького положительного числа, т.е. .
Следовательно, — точное решение уравнения (8).
3. Предположим, что уравнение (8) имеет два точных решения и .
.
.
Теорема доказана.
Частный случай. Пусть n = 1, т.е. система состоит из одного уравнения
f (x) = 0 с одной неизвестной x.
Уравнению равносильно x = g (x). Решение x T — точка пересечения графиков функций y = x и y = g (x).
x 1 = g (x 0), x 2 = g (x 1), …
На этом рисунке метод простых итераций сходится.
На следующем — нет.
Аналогом метода Зейделя является способ, когда координаты нового приближения вычисляются по очереди из одного уравнения системы:
|
|
.
§ 5. Системы нелинейных уравнений: метод Ньютона
Идея метода: Пусть — приближенное решение уравнения (7), достаточно близкое к искомому точному решению. В окрестности уравнение (7) заменяется линейным уравнением (вспомогательной линейной задачей), решение которого берется в качестве следующего приближения.
1 случай) m = 1, т.е. одно уравнение f (x) = 0 с одной неизвестной.
Пусть x0 — "хорошее" начальное приближение.
— линейное уравнение, заменяющее исходное
— решение линейного уравнения
— рекуррентная формула, метод Ньютона
Геометрическая иллюстрация метода:
На следующем рисунке показана ситуация зацикливания:
Общий случай)
Дано: (7)
Опр. Линейный оператор назовем производной отображения в точке , если при .
Действие линейного оператора совпадает с произведением матрицы A на вектор , где , ,
Пусть — точно решение уравнения (7);
— некоторое приближение, близкое к ;
тогда .
рекуррентная формула, метод Ньютона.
Замечание: Матрица A –1 (зависящая от ) существует тогда и только тогда, когда A невырожденная.
Теорема (о сходимости метода Ньютона) (без док-ва)
При выполнении условий:
"аналог сжимаемости": для некоторого a 1 ≥ 0, любого и любого , где ;
"аналог дифференцируемости": , для некоторого a 2 ≥ 0, любых ;
и при итерационный процесс Ньютона сходится с оценкой погрешности
.
§ 6. Методы спуска
По аналогии с методами спуска для системы линейных уравнений заменим задачу решения системы (7) задачей минимизации функции .
Идея методов спуска:
1) Выбирается начальное приближение ;
2) Выбирается направление, в котором убывает;
3) В этом направлении от выбирается следующее приближение ;
4) По рекуррентной формуле последовательно находят приближения ,…, ;
5) Последнее приближение .
1 способ) Покоординатный спуск
Пусть .
Подставим в значения всех координат , кроме первой переменной.
Получим функцию от одной переменной. Найдем ее точку минимума. Это будет x 1(1).
|
|
Затем подставим в x 1(1) и значения всех остальных координат , кроме второй переменной.
Получим функцию от одной переменной. Найдем ее точку минимума. Это будет x 1(2). Продолжая таким образом, получим . И т.д.
Проиллюстрируем поведение алгоритма для m = 2.
Модификации алгоритма:
1) Случайный покоординатный спуск — порядок переменных выбирается случайным образом.
2) "Метод муравьиной кучи" — покоординатный спуск выполняется для нескольких разных нулевых приближений.
Недостатки алгоритма:
1) Не гарантирует сходимости.
2) Не гарантирует приближение к глобальному экстремуму.
2 способ) Метод наискорейшего спуска.
Использует рекуррентную формулу , где – некоторый параметр, определяемый из условия:
.
3 способ) Условная минимизация
Задача: Найти точку , в которой достигается минимум , при условиях в виде неравенств или равенств:
Методы решения таких задач получили название математическое программирование.
Если все функции F, j, y являются линейными — линейное программирование. Если есть нелинейные функции — нелинейное программирование. Если искомое решение должно состоять из целых чисел — целочисленное программирование.
Глава V. Дифференциальные уравнения и системы
§ 1. Задача Коши для обыкновенных дифференциальных уравнений: применение формулы Тейлора
Задача Коши: Дано: — дифференциальное уравнение 1-го порядка;
— отрезок, на котором определена искомая y (x);
— начальное условие.
Найти: функцию y (x), удовлетворяющую уравнению и начальному условию.
Пусть f (x, y) — аналитическая в окрестности т.(x 0, y 0) (т.е. может быть представлена рядом по степеням (x – x 0) и (y – y 0).
Алгоритм:
1. Известна .
Найдем .
.
– – – – – – – – – – –
.
2. Подставляя (x 0, y 0) получим:
.
.
. (числовые значения)
.
– – – – – – – – – – –
.
3. По формуле Тейлора составим:
Замечание: Пусть R — радиус сходимости ряда . Если , то погрешность формулы не уменьшается при .
Дальнейшее обобщение алгоритма:
Пусть отрезок разбит на n частей, — точки деления (узлы).
1. На найдем .
Тогда .
2. На найдем .
Тогда .
И т.д.
n. На найдем .
Тогда .
Т.е. найден набор приближенных значений искомой функции в узлах .
§ 2. Метод Эйлера. Методы Рунге-Кутта
Пусть отрезок разбит на n частей,
— точки деления (узлы), .
При m = 1, формула из § 1 имеет вид:
— формула Эйлера.
Методы Рунге-Кутта — класс методов, включающий в себя метод Эйлера.
Общая идея методов:
Пусть даны параметры:
q, a2,…,aq; p 1,…, p q; bij, 0 < j < i £ q.
Найдем последовательно:
– – – – – – – – – – – – –
Тогда
Т.е. находят последовательно по рекуррентной формуле
Частные случаи:
1) q = 1, p 1 = 1 — метод Эйлера.
2) q = 2, p 1 = = p 2; a2 = 1 = b21
Обоснование справедливости формулы:
Заменим интеграл квадратурной формулой трапеций
т.к. получаем
Заменим в правой части по формуле Эйлера
Тогда
3) q = 2, p 1 = 0, p 2 = 1; a2 = = b21
Обоснование справедливости формулы:
Заменим интеграл квадратурной формулой прямоугольников
Заменим в правой части по формуле Эйлера
§ 3. Конечно-разностные методы
Задача: Дано:
Пусть отрезок разбит на n частей одинаковой длины h,
— узлы.
Найти: — значения y (x) в узлах.
Явные конечно-разностные методы используют соотношения вида
где коэффициенты , подбираются так, чтобы формула была точна для многочленов наивысшей степени.
Неявные конечно-разностные методы используют соотношения вида
где новое значение y k присутствует в обеих суммах.
Простейшие методы такого типа получаются на основе квадратурных формул интегрирования:
По формуле трапеций получаем
— неявный конечно-разностный метод.
Для использования формулы Симпсона применяют другое равенство
— неявный конечно-разностный метод.
Формулу прямоугольников применим также для равенства
—явный конечно-разностный метод.
Замечание: вторая и третья формулы имеют низкую сходимость, т.е. при уменьшении h погрешность уменьшается медленнее, чем в первой формуле.
§ 4. Уравнения второго порядка
I. Дифференциальное уравнение, в котором отсутствует .
Задача Коши: Дано:
, – начальные условия
Пусть отрезок разбит на n частей одинаковой длины h,
— узлы.
Найти: — значения y (x) в узлах.
Для каждого узла выполняется
Заменим в левой части вторую производную формулой численного дифференцирования по трем точкам:
Правую часть заменим линейной комбинацией
Тогда получим формулу
явный метод.
Если правую часть заменим другой линейной комбинацией , то получим формулу
неявный метод.
Коэффициенты подбираются так, чтобы формула была точна для многочленов наивысшей степени.
Пример. Метод Нумерова — неявный метод, m = 1, четвертого порядка точности.
Вывод формулы методом неопределенных коэффициентов:
Нужно найти формулу
точную для y (x), являющейся многочленом до четвертой степени.
Пусть x k = 0.
Для y (x) = x 2
Для y (x) = x 3
Для y (x) = x 4
Получается система
Решение системы:
Применение метода:
1) По формуле Эйлера находим .
2) По рекуррентной формуле находим
.
II. Задача Коши: Дано:
, – начальные условия
отрезок разбит на n частей одинаковой длины h,
— узлы.
Найти: — значения y (x) в узлах.
В ходе решения будут найдены также
значения в узлах.
Явный метод использует равенства
Неявный метод использует равенства
Пример. Явный метод, m = 0.