Вспомогательная задача.
многочлен степени
n.
Корни
Далее будем
обозначать
.
Чебышёвский процесс для вычисления решения системы.
Для решения задачи
минимакса примем в качестве параметра
множество нулей многочлена Чебышева
на отрезке
.
Воспользуемся многочленом
,
обладающим свойством
и построим этот многочлен.
Теорема 2.
Пусть , тогда рассматривая итерационный процесс следует выбрать итерационный параметр следующим образом:
При этом если число итераций n фиксировано, то достигается минимум:
– определено выше.
Замечание.
Особенность
многочлена Чебышева в том, что фиксируется
число итераций заранее и
.
Замечание.
Так как при
построении итерационных процессов
,
то выбор числа итераций
.
Замечание.
– решение с заданной
точностью. Число n
удваивают (в этом случае) не производят
вычисление ещё раз.
Замечание.
Существуют такие
наборы, как, например,
,
которые обеспечивают устойчивость
итерационных процессов.
Лекция № 11.
ИССЛЕДОВАНИЕ СКОРОСТИ СХОДИМОСТИ
ИТЕРАЦИОННЫХ МЕТОДОВ.
Основные определения.
– малое число, а
– достаточно большое число.
– число раз, в которое требуется уменьшить исходную погрешность.
Итерационные метод сходятся с геометрической скоростью сходимости.
– оценка числа
итераций.
Определение 1.
Скоростью сходимости
итерационного метода называется величина
S – матрица перехода.
Пример.
Метод простой итерации с оптимальным выбором параметра.
Чебышевский процесс.
Так как
,
то
при достаточно больших n
стремится к 1. Для оценки числа итераций
будем использовать:
Пример.
Метод Якоби.
Метод разойдётся, так как матрица не обладает свойством диагонального преобладания.
МПИ с оптимальным выбором параметра.
Если спектр (разброс) большой, то матрица плохо обусловлена.
Метод Зейделя.
создаётся за 66
итераций.
Метод с Чебышёвский набором параметров.
Оценим сначала число итераций.
Недостатком данного метода является то, что необходимо знать собственные числа матрицы.
Другие итерационные методы.
Неявный итерационный процесс.
В неявных методах матрица B называется предобусловливателем.
Метод минимальных невязок.
Определение 1.
Невязкой называется
вектор
.
Метод минимальных
невязок состоит в том, что параметр
выбирается из условия
при фиксированной норме невязки
.
Условие
экстремума
.
Теорема 1.
Метод минимальных поправок.
– поправка.
Лекция № 12.
ЧАСТИЧНАЯ ПРОБЛЕМА СОБСТВЕННЫХ ЗНАЧЕНИЙ.
Вспомогательные сведения.
P – матрица перехода от исходного базиса к базису из собственных векторов.
Утверждение 1.
Пусть
и
– различные собственные числа,
и
– собственные вектора и матрица A
самосопряженная
.
Тогда
.
Пример.
Собственные числа растут и, вообще говоря, задача поиска собственных чисел большая проблема.
Исчерпывание корней.
Находим хотя бы
один корень, делим
и опять применяем этот метод.
QR-алгоритм.
Рассмотрим матрицу:
Обозначим через
круг на комплексной плоскости с центром
в точке
.
Определение 1.
Кругом Гержгорина
называется множество комплексной
плоскости
.
Теорема 1.
Любые собственные значения матрицы A находятся в объединении кругов Гержгорина.
– максимальная
координата собственного вектора.
Следствие 1.
Если круг Гержгорина изолирован, то в нём находится одно собственное значение.
Следствие 2.
Если k кругов образуют замкнутую область, то там ровно k собственных значений матрицы A.
Для простоты пусть A – матрица простой структуры и пусть все собственные значения различны.
– максимальное
собственное значение.
Степенным методом называется метод (итерационный):
Теорема 2.
Пусть A
– матрица простой структуры и пусть
– базис из собственных векторов. Тогда
и справедлива оценка:
Докажем только сходимость.
Модификация:
Пример.
Лекция № 13.
РЕШЕНИЕ НЕЛИНЕЙНЫХ СИСТЕМ УРАВНЕНИЙ.
Постановка задачи.
Введём
Найти
приближение к
– точное решение, такое что
.
Выделяют два этапа:
Локализация корней.
Нахождение корня с заданной точностью.
Метод простой итерации (метод Якоби).
Пример.
Система для итераций.
Теорема 1.
Пусть в некоторой
окрестности корня
выполнены условия
.
Тогда МПИ сходится при любом начальном
приближении и справедлива оценка:
Следствие 1.
Критерий окончания
.
Для рассматриваемого примера.
Реализация решения на MathCAD.
Итерационные методы для решения систем нелинейных уравнений.
Метод Ньютона.
Пример.
В силу громоздкости вычислений чаще используется упрощенный метод Ньютона.
Нелинейный метод Якоби.
Решаем уравнение
как скалярное относительно
.
Метод Зейделя (нелинейный).
Модификация нелинейного метода Якоби.
Метод простой итерации в канонической форме.
Метод Ньютона-Зейделя.
Метод Пикара.
Пример.
Получили СЛАУ с одной и той же матрицей A и разными правыми частями на каждой n-ой итерации.
Лекция № 14.
РЕШЕНИЕ ПЕРЕОПРЕДЕЛЁННЫХ СИСТЕМ.
Линейная задача.
Переопределённая система – число уравнений больше числа неизвестных.
Определение 1.
Будем называть A
матрицей
полного столбцевого ранга,
если
.
– матрица полного
столбцевого ранга,
– единственное решение.
Определение 2.
Будем называть
вектором невязки
.
– решение системы,
в общем случае не существует.
Понимаем под
решением задачи вектор
.
Теорема 1.
Решением задачи
является вектор
,
удовлетворяющий системе уравнений
.
Если
– решение системы
,
то
– точка
.
Пример.
Докажем, что
– симметричная и положительно
определена.
Утверждение 1.
для матриц полного столбцевого ранга имеет единственное решение.
Нелинейная задача метода наименьших квадратов.
Сведём к линейной задаче, выполнив линеаризацию по Ньютону:
Критерий окончания
Вводится вектор поправки:
Алгоритм решения:
Найдена
.
Вычисляем
.
Получаем
.
Упрощённый метод Ньютона.
Пример.
Постановка задачи минимизации функций.
Необходимое условие
экстремума
.
Определение 3.
Методы, использующие производные, называются градиентными.
Определение 4.
называется
унимодальной
на
,
если существует
,
для которого выполняются условия:
Определение 5.
Точка
– точка локального минимума, если в
определении точки выполняется условие
.
Метод биекции поиска точки минимума.
Утверждение 2.
Пусть внутри
и
.
Если
,
то берём отрезок
,
иначе
.
Алгоритм метода
биекции аналогичен методу половинного
деления с выбором параметра
итерационного процесса
.
Лекция № 15.
МЕТОДЫ МИНИМИЗАЦИИ.
Методы поиска.
Утверждение 1.
Сужение отрезка унимодальных функций.
Если
,
то
,
в противном случае
.
Пассивный поиск.
Если
,
то оптимальный поиск
.
Метод биекции.
Применяем утверждение о сужении отрезка.
Если
,
то
,
в противном случае
.
Теорема 1.
Пусть
– унимодальная на
и
.
Тогда справедлива оценка
.
Доказывается методом индукции.
Метод золотого сечения.
Определение 1.
Золотым сечением
отрезка называется деление отрезка в
отношении
.
Алгоритм метода золотого сечения:
Пусть на k-ом
шаге выбран отрезок
.
Тогда либо
,
либо
.
Сужение отрезка в соответствии с
утверждением.
Критерий окончания
,
но при этом
берётся равным
.
Оценка погрешности
метода
.