Файл: Численные методы.pdf

корня итерационная последовательность не выходит за пределы этой окрестности, метод сходится и справедлива оценка

окрестности знак вычисленного значения f*(x) не обязан совпадать со знаком f(x) и, следовательно, становится невозможным определить какое именно значение х из интервала обращает функцию в нуль. Этот интервал называется интервалом неопределенности корня .

6. Метод бисекции решения нелинейного уравнения: алгоритм, геометрическая иллюстрация, условия и скорость сходимости (с доказательством).

Описание метода: пусть требуется с заданной точность ε>0 найти корень уравнения. Отрезок локализации [a,b] (т.е. отрезок, содержащий только один корень ) будем считать заданным. Предположим что функция f непрерывна на отрезке и на его концах принимает значения разных знаков, т.е. f(a)f(b)<0.

Из этой оценки видно, что метод бисекции сходится со скоростью геометрической прогрессии, знаменатель которой равен q=1/2. По сравнению с другими методами, метод бисекции сходится довольно медленно.

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

7. Метод простой итерации решения нелинейного уравнения. Достаточное условие сходимости, априорная и апостериорная оценки погрешности (с доказательствами), критерий окончания, приведение к виду, удобному для итераций.

Описание метода: чтобы применить метод простой итерации для решения нелинейного уравнения, необходимо преобразовать это уравнение к виду x=ϕ(x). Это преобразование (приведение уравнение к виду, удобному для итераций) можно выполнить различными способами. Функцию ϕ называют итерационной функцией.

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

по формуле . Если существует предел построенной последовательности

Сходимость метода:

Теорема: Пусть в некоторой σ-окрестности корня функция ϕ дифференцируема и удовлетворяет неравенству

Где 0<q<1 – постоянная. Тогда независимо от выбора начального приближения из указанной окрестности корня итерационная последовательность не выходит из этой окрестности, метод

сходится со скоростью геометрической прогрессии и справедлива следующая оценка погрешности:

Доказательство: использую формулу конечных приращений Лагранжа, получаем

Оценка погрешности является априорной. Она показывает, что метод простой итерации сходится со скоростью геометрической прогрессии, знаменатель которой равен q. Чем меньше q, тем выше скорость сходимости.

Доказательство: в силу равенства из предыдущего доказательства имеем

Откуда

Взяв модуль от левой и правой частей этого равенства, и воспользовавшись неравенством

И получаем требуемое соотношение.

Приведение уравнения к виду, удобному для итераций:

Предположим что производная f’ на отрезке [a,b] непрерывна и положительна. Тогда существуют положительные постоянные m и M такие, что 0<m<f’(x)<M при x принадлежащему

8. Метод Ньютона решения нелинейного уравнения. Теорема о сходимости (без доказательства), априорная и апостериорная оценки (с доказательствами), критерий окончания, геометрическая интерпретация, трудности использования.

Метод Ньютона делится на два подхода: метод касательных и метод линеаризации.

Метод касательных:

примем абсциссу точки пересечения касательной с осью Ох. Продолжая этот процесс далее,

Выражая из него , получаем расчетную формулу метода Ньютона:

Метод линеаризации: метод Ньютона можно рассматривать как итерационный метод.

Пусть приближение уже получено. Представим функцию в окрестности точки по формуле Тейлора:

Здесь ξ – некоторая точка, расположенная между x и . Заменяя в уравнении f(x)=0 функцию f(x) главной линейной частью разложения, получаем линейное уравнение

Теорема о сходимости: пусть - простой корень уравнения f(x)=0, в некоторой окрестности которого функция f дважды непрерывно дифференцируема. Тогда найдется такая малая σ-

окрестность корня , что при произвольной выборе начального приближения из этой окрестности итерационная последовательность метода Ньютона не выходит за пределы окрестности и справедлива оценка

Означающая, что метод сходится с квадратичной скоростью. Следствием оценки является априорная оценка

непрерывности функции f’ и f’’ найдется δ-окрестность корня, в которой при некоторых

Подставляя x= в формулу Тейлора, получаем равенство

Тогда, приравнивая модули обеих частей этого равенства и используя условия ограниченность модулей производных, приходим к неравенству

Откуда следует справедливость оценки.

На практике предпочтительнее использование простой апостериорной оценки

Поэтому применяя неравенство априорной оценки получаем цепочку неравенств

Из которой вытекает апостериорной оценки. Вычисление нужно вести до тех пор, пока не окажется выполнено неравенство

Трудности использования:

1)Иногда невозможно найти аналитическое выражение для f(x) (взять производную).

2)Метод Ньютона обладает только локальной сходимостью, то есть область его

сходимости является некоторая малая σ окрестность корня и для гарантии сходимости необходимо выбирать хорошее начальное приближение. Неудачный выбор может дать расходящуюся последовательность.

9) Модификации метода Ньютона (упрощенный метод Ньютона, метод ложного положения, метод секущих, метод Стеффенсена). Поиск кратных корней.

Упрощенный метод Ньютона: если производная непрерывна, то ее значение вблизи простого корня почти постоянно. Поэтому можно попытаться вычислить f’ лишь однажды в

точке , а затем заменить в формуле значение постоянной .

В основе следующих модификаций лежит приближенное равенство

Верно при условии и следует из определения производной. Пусть с – фиксированная точка, в окрестности корня. Заменим производную в формуле метода Ньютона приближенным равенством, полагая . В результате получим метод ложного положения:

Метод Стефенсена: итерационная формула имеет вид

Уточнение метода Ньютона для случая кратного корня

При m>1 скорость сходимости стандартного метода становится линейной. Чтобы сохранить квадратичную скорость, метод Ньютона нужно модифицировать следующим образом:

а) стандартный метод, б) уточненный метод.

10) Решение СЛАУ. Постановка задачи. Нормы векторов и матриц. Понятие о прямых и итерационных методах решения.

Ввычислительной линейной алгебре традиционно выделяют четыре основные задачи:

1)Решение систем линейных алгебраических уравнений

2)Вычисление определителей

3)Нахождение обратных матриц

4)Определение собственных значений и собственных векторов

В последнее время к ним добавились еще две:

5)Линейная задача метода наименьших квадратов

6)Вычисление сингулярных чисел и сингулярных векторов.