Необходимые и достаточные условия сходимости итерационных методов.

Теорема 3.1. Для того чтобы метод простой итерации сходился необходимо и достаточно чтобы все собственные значения матрицы B=E-D -1 A были по модулю меньше единицы.

Доказательство. Пусть X ( k ) → X * . Тогда, как мы видели, X * есть решение системы и, следовательно,

откуда B k (X * — X (0) )→0. Так как это должно иметь место при любом векторе X (0) , Необходимо, чтобы B k →0, длячего, в свою очередь, необходимо, чтобы все собственные значения матрицы B были меньше единицы по модулю.

Достаточность условия непосредственно вытекает из формулы

т.к.B k →0 и E+B+ …+ B k →(E – B) -1 =A -1 ,если все собственные значения матрицы B меньше единицы по модулю.

Так как условие теоремы 3.1 трудно проверяется, судить о сходимости процесса последовательных приближений лучше при помощи достаточных признаков, связанных непосредственно с элементами матрицы В. Некоторые достаточные признаки вытекают из теоремы 3.1

Теорема 3.2. Для того чтобы процесс последовательных приближений сходился, достаточно, чтобы какая-либо норма матрицы В была меньше единицы.

Доказательство. Действительно, если ||B|| ( k ) ||≤||B|| k ||X (0) ||+. (3.4)

Доказательство. Имеем ||X*-X ( k ) ||=||(E-B) -1 G-(E+B+…+B k -1 )G-B k X (0) ||≤

≤||(E-B) -1 G -(E+B+…+B k -1 )G||+||B k X (0) ||≤||(E-B) -1 G-(E+B+…+B k -1 )G||+||B k |X (0) ||≤

≤||B|| k ||X (0) ||+ .

Часто бывает важно сравнить точность двух последовательных приближений, т.e. сравнить величины ||X*-X ( k ) || и ||X*-X k -1 ||. Taкое сравнение можно проводить наосновании следующей теоремы.

Теорема 3.4 ||X*-X ( k ) ||≤||B|| ||X*-X k -1 ||.

Доказательство. Действительно, из равенств

Материал из MachineLearning.

Содержание

Постановка задачи

Пусть есть функция .
Требуется найти корень этой функции: такой при котором
Решение необходимо найти численно, то есть для реализации на ЭВМ. Для решения этой задачи предлагается использовать метод простых итераций.

Метод простых итераций в общем виде

Заменим исходное уравнение на эквивалентное ,и будем строить итерации по правилу . Таким образом метод простой итерации — это одношаговый итерационный процесс. Для того, что бы начать данный процесс, необходимо знать начальное приближение . Выясним условия сходимости метода и выбор начального приближения.

Сходимость метода простых итераций

Метод сходится, если при последовательность < >имеет предел.
Обозначим окресность точки радиуса , то есть .
Теорема 1. Если липшиц-непрерывна с константой на , то есть выполняется

при этом если также выполнено

, то уравнение имеет единственное решение на и метод простой итерации сходится к решению при любом выборе начального приближения .Так же справедлива оценка: ,

где — точное решение.

Из оценки видно, что метод линеен. Пусть непрерывно дифференцируема на , тогда из теоремы вытекают следующие утверждения:
Следствие 1. Если для , выполнено , и , тогда уравнение имеет единственное решение на и метод простой итерации сходится к решению.

Следствие 2. Если уравнение имеет решение , непрерывно дифференцируема на и . Тогда существует 0" alt= "eps > 0" /> такое, что на уравнение не имеет других решений и метод простой итерации сходится к решению при

Геометрическая интерпретация

Рассмотрим график функции . Это озночает, что решение уравнения и — это точка пересечения с прямой :

И следующая итерация — это координата пересечения горизонтальной прямой точки с прямой .

Из рисунка наглядно видно требование сходимости . Чем ближе производная к , тем быстрее сходится алгоритм. В зависимости от знака производной вблизи решения приближения могут строится по разному. Если , то каждое следующее приближение строится с другой стороны от корня:

Метод релаксации

Где не меняет знака на отрезке, на котором ищется корень функции.
Положим и рассмотрим метод в этом случае.
Тогда получим метод ‘релаксации’:

для которого , и метод сходится при условии

Пусть в некоторой окресности корня выполняются условия

Тогда метод релаксации сходится при

Выбор параметра

Оценим погрешность метода релаксации

Применяя теорему о среднем получаем

Таким образом задача сводится к нахождению минимума функции

Из рассмотрения графика функции видно, что точка минимума определяется

Ускорение сходимости

Как следует из Теоремы 1, метод простых итераций линеен, то есть

Воспользуемся этим для оценки погрешности на каждой итерации. Запомним 3 последние итерации и выпишем их оценки:

Где нам известны (вычисленны по какому то линейному алгоритму),а найдем из системы. Получим:

Метод ускорения сходимости заключается в том, что после вычисления 3 приближений по линейно сходящемуся алгоритму, вычисляется новое приближение по уточняющему правилу (2).
Применительно к методу релаксации имеем:

Можно показать, что данный метод имеет уже квадратичную скорость сходимости.

Метод Вегстейна

Метод Вегстейна, вообще говоря, является модификацией метода секущих, однако его можно назвать и улучшенным методом простой итерации, преобразовав вычислительню формулу

Это двухшаговый метод, и для начала вычислений необходимо задать 2 приближения .

Программная реализация

Все методы были реализованы на языке C++. Доступ к методам осуществяется через класс

Примеры тестирования

Ошибкой будем считать и проверим скорость сходимости методов относительно друг друга.

Начальное приближение
1. Метод простой итерации с .
Сходимость за 28 шагов.
2. Метод простой итерации с .
Сходимость за 21 шаг.
3. Ускоренный метод простой итерации.
Сходимость за 3 шага.
4. Метод Вегстейна.
Сходимость за 3 шага.

Корень

Начальное приближение
1. Метод простой итерации с .
Сходимость за 23 шагов.
2. Метод простой итерации с .
Сходимость за 5 шаг.
3. Ускоренный метод простой итерации.
Сходимость за 4 шага.
4. Метод Вегстейна.
Сходимость за 4 шага.

Корень

Начальное приближение
1. Метод простой итерации с .
Сходимость за 43 шагов.
2. Метод простой итерации с .
Сходимость за 7 шагов.
3. Ускоренный метод простой итерации.
Сходимость за 5 шагов.
4. Метод Вегстейна.
Сходимость за 7 шагов.

Исходный код можно скачать Код программы

Понятие«вычислительная задача». Типы вычислительных задач и их постановка.

Решение задачи с помощью компьютера — это процесс автоматического преобразования исходной информации (исходных данных) в искомый результат в соответствии с заданной последовательностью выполнения действий, называемой алгоритмом. Вычислительные задачи связаны с вычислением в традиционном (арифметическом) смысле этого слова неизвестного значения информационного объекта (переменной, функции и т.д.). Основными элементарными операциями, выполняемыми при решении таких задач, являются арифметические операции сложения, вычитания, умножения, деления, возведения в степень и т.д. В постановке вычислительной задачи выделяют три обязательных элемента: условие задачи, известные данные (исходные данные) и неизвестное (неизвестные). Условие задачи представляет собой явно или неявно выраженное соотношение между данными и неизвестными задачи.

Условия корректности вычислительной задачи.

Корректность. Определим вначале понятие устойчивости решения.

Решение задачи y* называется устойчивым по исходным данным x*, если оно зависит от исходных данных непрерывным образом. Это означает, что малому изменению исходных данных соответствует малое изменение решения. Строго говоря, для любого e > 0 существует d = d(e) > 0 такое, что всякому исходному данному x*, удовлетворяющему условию |x — x*|

Говорят, что задача поставлена корректно, если выполнены следующие три условия:

1. Решение существует при любых допустимых исходных данных.

2. Это решение единственно.

3. Это решение устойчиво по отношению к малым изменениям исходных данных.

Если хотя бы одно из этих условий не выполнено, задача называется некорректной.

Метод Гаусса решения систем линейных алгебраических уравнений: класс метода, прямой и обратный ходы, оценка трудоемкости.

Метод последовательного исключения неизвестных Гаусса является одним из универсальных, точных и прямых методов, позволяющих за конечное количество действий получить точное решение системы.

Решение по этому методу выполняется в два хода: прямой и обратный.

При прямом ходе исходная система уравнений:

приводится к эквивалентной системе с треугольной матрицей коэффициентов:

При обратном – из эквивалентной системы идёт последовательное, начиная с конца, определение неизвестных xj, j= n, n – 1, …, 1 по следующим рекуррентным формулам:

– при j= n получаем

– при j=n – 1, n – 2, … , 1 получаем

Трудоёмкость метода Гаусса

Количество действий прямого хода:

Количество действий обратного хода:

.

Суммарное количество действий:

Здесь n – количество уравнений (порядок) системы.

Метод простых итераций решения систем линейных алгебраических уравнений: класс метода, оценка трудоемкости, условие сходимости, получение начального приближения, алгоритм решения, условие окончания.

Это приближённый метод. Он позволяет получить решение сис-темы линейных алгебраических уравнений с погрешностью, не превышающей заданную допустимую величину ε, за ограниченное количество итераций.

Имеем исходную систему уравнений:

(1.5)

Запишем систему (1.5) в матричной форме:

Можно представить исходную систему матричным уравнением

или в развёрнутой матричной форме

Вектор-столбец в правой части с нулевыми значениями элементов получается, когда векторX есть точное решение системы. В противном случае получим вектор-«невязок»

Обозначим через Z вектор приближённых значений решения системы. Вначале это будет нулевое приближение – вектор Z (0) . В качестве начального приближения решения системы можно брать .

При подстановке в систему (1.8) на место X вектора Z (0) получим:

(1.9)

где – вектор-«невязок» начального (нулевого) приближения относительно точного решения.

Цель и суть метода простых итераций – сведение к нулю «невязок» в решении системы (1.9). Практически стремятся к выполнению условия

где S – номер итерации, S = 0, 1, 2, …

где j – номер слагаемого скалярного произведения i-той строки матрицы A на вектор Z.

Условие сходимости метода простых итераций

Метод простых итераций сходится при условии, что диагональные коэффициенты матрицы A исходной системы по абсолютной величине больше суммы абсолютных величин других коэффициентов в своей строке:

Дата добавления: 2018-04-15 ; просмотров: 501 ; ЗАКАЗАТЬ РАБОТУ