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

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

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

Рассмотрим соответствующую однородную систему:

, 2626\* MERGEFORMAT ()

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

, , . 2727\* MERGEFORMAT ()

Запишем -ое уравнение системы 26 в виде

и возьмем модуль от обеих частей этого равенства. В результате получим:

. 2828\* MERGEFORMAT ()

Сокращая неравенство 28 на множитель , который, согласно 27, не равен нулю, придем к противоречию с неравенством 25, выражающим диагональное преобладание. Полученное противоречие позволяет последовательно высказать три утверждения:

1. Однородная система 26 с диагональным преобладанием имеет только тривиальное решение.

2. Определитель матрицы с диагональным преобладанием не равен нулю.

3. Неоднородная система 2 с диагональным преобладанием всегда разрешима и притом единственным образом.

Последнее из них означает, что доказательство теоремы завершено.

1. Системы с трехдиагональной матрицей. Метод прогонки.

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

, , 2929\* MERGEFORMAT ()

, , 3030\* MERGEFORMAT ()

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

; ,

где - заданные числа. Однако, чтобы не усложнять изложение, мы ограничимся простейшей формой дополнительных условий 30.

Пользуясь тем, что значения и заданы, перепишем систему 29 в виде:

3131\* MERGEFORMAT ()

Матрица этой системы имеет трёхдиагональную структуру:

3232\* MERGEFORMAT ()

Это существенно упрощает решение системы 29 благодаря специальному методу, получившему название метода прогонки.

Метод основан на предположении, что искомые неизвестные и связаны рекуррентным соотношением

, . 3333\* MERGEFORMAT ()

Здесь величины , , получившие название прогоночных коэффициентов, подлежат определению, иcходя из условий задачи 29, 30. Фактически такая процедура означает замену прямого определения неизвестных задачей определения прогоночных коэффициентов с последующим расчетом по ним величин .

Для реализации описанной программы выразим с помощью соотношения 33 через :

и подставим и , выраженные через , в исходные уравнения 29. В результате получим:

,

.

Последние соотношения будут заведомо выполняться и притом независимо от решения, если потребовать, чтобы при имели место равенства:

Отсюда следуют рекуррентные соотношения для прогоночных коэффициентов:

, , . 3434\* MERGEFORMAT ()

Левое граничное условие и соотношение непротиворечивы, если положить

. 3535\* MERGEFORMAT ()

Остальные значения коэффициентов прогонки и находим из 34, чем и завершаем этап вычисления прогоночных коэффициентов.

Далее, согласно правому граничному условию

. 3636\* MERGEFORMAT ()

Отсюда можно найти остальные неизвестные в процессе обратной прогонки с помощью рекуррентной формулы 33.

Число операций, которое требуется для решения системы общего вида 2 методом Гаусса, растет при увеличении пропорционально . Метод прогонки сводится к двум циклам: сначала по формулам 34 рассчитываются прогоночные коэффициенты, затем с их помощью по рекуррентным формулам 33 находятся компоненты решения системы . Это означает, что с увеличением размеров системы число арифметических операций будет расти пропорционально , а не . Таким образом, метод прогонки в пределах сферы своего возможного применения является существенно более экономичным. К этому следует добавить особую простоту его программной реализации на компьютере.

Во многих прикладных задачах, которые приводят к СЛАУ с трехдиагональной матрицей, ее коэффициенты удовлетворяют неравенствам:

, 3737\* MERGEFORMAT ()

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

Согласно теореме предыдущего раздела решение таких систем всегда существует и является единственным. Для них также справедливо утверждение, которое имеет важное значение для фактического расчета решения с помощью метода прогонки.

Лемма

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

. 3838\* MERGEFORMAT ()

Доказательство проведем по индукции. Согласно 35 , т. е. при утверждение леммы верно. Допустим теперь, что оно верно для и рассмотрим :

. 3939\* MERGEFORMAT ()

Итак, индукция от к обоснована, что и завершает доказательство леммы.

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

1. Обусловленность СЛАУ.

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

1. Норма матрицы.

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

4040\* MERGEFORMAT ()

и евклидова норма

, 4141\* MERGEFORMAT ()

удовлетворяющая трем аксиомам нормы:

1. , тогда и только тогда, когда ;

2. ;

3. (неравенство треугольника).

Для скалярного произведения справедливо неравенство Коши-Буняковского .

Рассмотрим квадратную матрицу размером . Она определяет в пространстве линейное преобразование

4242\* MERGEFORMAT ()

или

.

Введем величину

, 4343\* MERGEFORMAT ()

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

,

где вектор единичной длины: , получим представление для нормы, эквивалентное 43

. 4444\* MERGEFORMAT ()

Отсюда следует, что в конечномерном пространстве норма матрицы ограничена, причем на единичной сфере всегда найдется такой вектор , что

.

Наконец, из определения нормы 43 следует, что

. 4545\* MERGEFORMAT ()

Это простое неравенство лежит в основе всех дальнейших оценок.

1. Корректность решения СЛАУ.

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

1. Решение задачи существует.

2. Решение задачи единственное.

3. Решение задачи непрерывно зависит от входных данных.

Обсудим с точки зрения этого определения задачу решения СЛАУ с неравным нулю определителем

, 4646\* MERGEFORMAT ()

считая матрицу фиксированной и рассматривая в качестве входных данных вектор правых частей системы .

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

. 4747\* MERGEFORMAT ()

Пусть теперь правая часть подверглась возмущению и стала равной . Тогда, согласно 47, решение возмущенной системы

4848\* MERGEFORMAT ()

тоже можно записать через обратную матрицу :

, 4949\* MERGEFORMAT ()

где

. 5050\* MERGEFORMAT ()

Отсюда получаем

. 5151\* MERGEFORMAT ()

Неравенство 51 доказывает непрерывную зависимость возмущения решения от возмущения правой части :

при . 5252\* MERGEFORMAT ()

Это означает, что решение СЛАУ с неравным нулю определителем - корректная математическая задача: для нее выполняются все три требования корректности Адамара.

1. Число обусловленности матрицы.

Исходное уравнение 46 позволяет написать неравенство:

. 5353\* MERGEFORMAT ()

Перемножая его с неравенством того же знака 51, получим:

. 5454\* MERGEFORMAT ()

Пусть , тогда, согласно 47, и неравенство 54 можно переписать в виде:

, 5555\* MERGEFORMAT ()

где

. 5656\* MERGEFORMAT ()

Число называется числом обусловленности матрицы . Оно позволяет оценить относительную погрешность решения через относительную погрешность возмущения правой части. Поскольку исходная система 46 линейная, оценка относительной погрешности является более естественной, чем оценка абсолютной погрешности. Чем больше , тем резче реагирует решение на возмущение правой части. Поэтому матрицы с большим числом обусловленности и соответствующие им СЛАУ называют плохо обусловленными. Для оценки роли, которую играет число обусловленности при решении линейных алгебраических систем, разберем задачу.

Задача 1

Рассмотреть систему двух уравнений

, , 5757\* MERGEFORMAT ()

и соответствующую ей возмущенную систему

, , . 5858\* MERGEFORMAT ()

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

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