Дискретно-непрерывная математика (стр. 118 )

Это было доказано выше для і= 1. Для i > 1 заметим, что в силу (17)

матрица имеет нужные значения по крайней мере в тех же строках, что и а матрица — по крайней мере в тех же строках, что . Тогда для і-го столбца матрицы получаем из (17), что

Таким образом, самое большее через 2п— 1 шаг мы получим точное решение.

Следующая теорема показывает, что данный метод обладает так называемым «квадратичным» свойством сходимости, хорошо знакомым по методу Ньютона — Рафсона.

Теорема 6. Пусть

Тогда для метода (17) имеет место

где α — неотрицательное вещественное число, не зависящее от т, т. е. на каждом шаге ширина интервала примерно возводится в квадрат.

Доказательство (методом математической индукции). Из (17) мы получаем

(17')

Положим теперь при

(17")

и наконец

Используя определение (17"), мы немедленно получаем из (17') при і= 1, что

и

Допустим теперь, что для первых і≠1 строк и столбцов имеет место при

(17'")

Это очевидно при і=1. Теперь мы получаем из (17') и (17"), что

Аналогично

Из этих соотношений следует доказываемое утверждение

Если исполнять (17) на вычислительной машине, применяя машинную интервальную арифметику, то в противоположность теореме 5 мы, вообще говоря, не получим за конечное число ша­гов точного треугольного разложения матрицы . Рассмотрим, какой окончательной точности здесь можно достичь. В этих рас­суждениях примем те же допущения, которые привели нас к формулам (4 15а) и (4 15Ь), а тем самым и к (4 22), (4.23). По­следние две формулы были использованы при доказательстве формул (4 24) и (4.25). Теперь мы применим эти две формулы к (17). Это дает ширину вычисленных элементов

В этих неравенствах Sj и , обозначают фактические ре­зультаты промежуточных вычислений. Эти неравенства можно интерпретировать следующим образом. Допустим, что все эле­менты матрицыне превосходят 1 по абсолютной величине. Это предположение выполняется хотя бы приближенно, если строки матрицы упорядочены таким образом, что не прихо­дится переставлять строки в процессе исключения по Гауссу с выбором главных элементов по столбцам. Если ширина интер­валов не слишком велика, то не намного больше 1, а в силу того, что в (17) берутся пересечения, это верно и для При тех же предположениях те же рассуждения пока­зывают, что малы. Поэтому делаем вывод, что при малой ширине элементов на m-м шаге разность между существенно зависит от и от величины промежуточных результатов. То же верно и для разности между если добавить еще, что малые величины могут ухудшить эту разность.

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

(a) Элементы матрицы по абсолютной величине не на­много больше единицы.

(b) Диагональные элементы матрицы по абсолютной величине не намного меньше единицы.

(c) Элементы матрицыпо абсолютной величине не боль­ше единицы.

(d) Вычисленные промежуточные результаты в (17) не слишком велики по абсолютной величине.

Модуль 10

Методы Ньютоновского типа

Микромодуль 37

Методы Ньютоновского типа для системы нелинейных уравнений

Рассмотрим методы итерационной локализации решений для систем нелинейных уравнений. Дано множество функций векторной переменной которые мы объединим в векторную функцию

Допустим, что производная Фреше функ­ции существует на множестве и что

Мы предположим также, что для

производной Фреше имеется интервальная оценка на Пусть теперь дан вектор

удовлетворяющий уравнению

(1)

При сделанных предположениях мы можем линейно аппрок­симироватьв точке с помощью формулы Тей­лора

(2)

Из (1) следует, что вектор ур удовлетворяет уравнению

где матрица определяется равенством

(3)

Вместо будем иногда писать

так как эта матрица зависит от всех величин, входящих в ее определение. Так как величинылежат в открытом интервале (0, 1), имеем

Пусть интервальная матрица обозначает интервальное оценивание производной Фреше на интервале Тогда среди решениймножества линейных уравнений

(4)

имеется и вектор так как Теперь возникла

задача — вычислить вектор х(1), локализующий множество ре­шений уравнения (4), а затем использовать этот интервальный вектор как потенциально лучшую локализацию вектора-решения Перед тем как браться за эту задачу, мы рассмотрим еще одну возможность построения множества уравнений, аналогич­ного (4). В этом случае применяется линейная аппроксимация значения в точке несколько отличная от (2).