Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (doc) (1113731), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Свойство самосопряженности преобразования равносильно в этом случае выполнению условия совпадения матриц и :

, ,

Как известно, любая матрица представима в виде:

, 7878\* MERGEFORMAT ()

где

, . 7979\* MERGEFORMAT ()

Нетрудно видеть, что

8080\* MERGEFORMAT ()

В дальнейшем мы будем опираться на следующие важные свойства самосопряженных преобразований:

а) все собственные значения самосопряженного линейного преобразования (характеристические числа матрицы ) вещественны;

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

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

, , . 8181\* MERGEFORMAT ()

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

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

, . 8282\* MERGEFORMAT ()

Условимся обозначать собственные векторы линейного преобразования с матрицей как , её характеристические числа как , координаты произвольного вектора в ортонормированном базисе из собственных векторов как .

Для дальнейшего рассмотрения будут полезны три леммы.

Лемма 1.

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

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

.

Достаточность. Расположим для определенности все характеристические значения матрицы в порядке убывания:

.

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

, , .

Поэтому, очевидно, что .

Лемма 2.

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

. 8383\* MERGEFORMAT ()

Доказательство предлагается провести самостоятельно.

Лемма 3.

Если , то всегда найдется постоянное число , такое что

, 8484\* MERGEFORMAT ()

Доказательство.

Если , то достаточно положить . В общем случае напомним, что согласно 80

,

где , поэтому согласно предыдущей лемме

,

где - минимальное характеристическое число матрицы . Полагая, что , приходим к требуемому неравенству 84.

1. Достаточные условия сходимости итерационного процесса.

В этом разделе мы рассмотрим стационарный итерационный процесс 66, когда матрица и итерационный параметр не зависят от индекса , и докажем следующую теорему о достаточных условиях его сходимости.

Теорема Самарского

Пусть - самосопряженная положительно определенная матрица:

, , 8585\* MERGEFORMAT ()

- положительно определенная матрица, - положительное число:

, . 8686\* MERGEFORMAT ()

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

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

, , . 8787\* MERGEFORMAT ()

т. е. оно, в частности, предполагает, что матрица является положительно определенной. Кроме того, неравенство 87 определяет интервал, в котором может изменяться параметр :

. 8888\* MERGEFORMAT ()

После этих замечаний перейдем к доказательству теоремы. Выразим из соотношения 70 через :

и подставим в рекуррентную формулу для итерационной последовательности 66. В результате получим:

. 8989\* MERGEFORMAT ()

Отличие итерационной формулы 89 от 66 заключается в том, что она является однородной.

Матрица - положительно определенная. Следовательно она невырожденная и имеет обратную . С ее помощью рекуррентное соотношение 89 можно разрешить относительно :

, 9090\* MERGEFORMAT ()

где

, так что . 9191\* MERGEFORMAT ()

Умножая обе части равенства 90 слева на матрицу , получим еще одно рекуррентное соотношение

. 9292\* MERGEFORMAT ()

Рассмотрим последовательность положительных функционалов:

. 9393\* MERGEFORMAT ()

Составим аналогичное выражение для и преобразуем его с помощью рекуррентных формул 90 и 92:

9494\* MERGEFORMAT ()

Из самосопряженности матрицы и формулы 91 следует

В результате формула 94 принимает вид:

9595\* MERGEFORMAT ()

Таким образом, последовательность функционалов с учетом условия образует монотонно невозрастающую последовательность, ограниченную снизу нулем

. 9696\* MERGEFORMAT ()

Поэтому она сходится. Далее, согласно лемме 3

,

где - строго положительная константа. В результате, согласно 95 и 96 будем иметь

9797\* MERGEFORMAT ()

Из этого неравенства и сходимости последовательности функционалов следует, что при . В свою очередь , так что

Теорема доказана.

1. Метод простой итерации.

Такое название получил метод, при котором в качестве матрицы выбирается единичная матрица: , а итерационный параметр предполагается независящим от номера итерации . Иными словами, метод простой итерации – это явный стационарный метод, когда очередная итерация вычисляется по рекуррентной формуле

9898\* MERGEFORMAT ()

Будем считать, что матрица удовлетворяет условию теоремы Самарского, , тогда формула 88, определяющая границу интервала сходимости по итерационному параметру , принимает вид

. 9999\* MERGEFORMAT ()

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

100100\* MERGEFORMAT ()

Разложим вектор по базису собственных векторов

,

тогда

,

и

.

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

. 101101\* MERGEFORMAT ()

Дальнейшее исследование метода простой итерации построим на конкретном анализе рекуррентной формулы 98. Введем матрицу оператора перехода

, 102102\* MERGEFORMAT ()

и перепишем формулу 98 в виде

. 103103\* MERGEFORMAT ()

При этом погрешность будет удовлетворять аналогичному рекуррентному соотношению, только однородному

. 104104\* MERGEFORMAT ()

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

Лемма 1

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

. 105105\* MERGEFORMAT ()

Доказательство элементарно. Оно проводится прямой проверкой

При самосопряженной матрице матрица также является самосопряженной 102. Следовательно, ее норма определяется наибольшим по модулю собственным значением 105:

. 106106\* MERGEFORMAT ()

Лемма 2

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

, 107107\* MERGEFORMAT ()

Достаточность. Условие 107 означает, что норма матрицы , согласно 106, будет меньше единицы: . В результате получаем

, при . 108108\* MERGEFORMAT ()

Необходимость. Допустим, что среди собственных значений 105 нашлось хотя бы одно , которое не удовлетворяет условию леммы 107, т. е.

.

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

, .

т. е. . Необходимость выполнения неравенства 107 для всех собственных значений для сходимости метода простой итерации доказана.

Лемма 2 определяет программу дальнейшего исследования сходимости метода простой итерации: нужно установить диапазон изменения параметра при котором все собственные значения удовлетворяют неравенству 107. Это легко сделать. На рис. 1 приведены графики убывающих линейных функций 105. Все они выходят из одной точки , и идут вниз из-за отрицательных коэффициентов при , причем быстрее всех убывает функция . Когда она принимает значение , условие 107 для нее перестает выполняться:

, при .

Характеристики

Список файлов лекций