Приложение е

(рекомендуемое)

Метод квадратного корня

Пусть дана система

,

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

,

где - верхняя треугольная матрица, - нижняя треугольная матрица, транспонированная к матрице , т.е.

,

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

Вычисление элементов матрицы возможно лишь в строго определенном порядке. Схематически изобразим его так:

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

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

11) . Отсюда находим .

12) . Отсюда . И т.д. для элементов первой строки.

1j) . Отсюда .

Для элементов второй строки:

22) . Отсюда находим .

2j) . Отсюда .

Теперь мы можем обобщить эти выражения. Для элементов -ой строки (элементы предыдущих строк уже найдены):

ii) . Отсюда находим .

ij) . Отсюда .

Отметим здесь же, что элементы матрицы будут действительны, если все . Это имеет место, если матрица положительно определена. Наиболее часто описываемый метод применяют именно в этом случае. Если же для некоторой строки окажется , то последующие элементы окажутся комплексными. Однако, метод формально применим и в этом случае.

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

.

Она эквивалентна последовательному решению двух систем:

, ,

или, в раскрытом виде,

,

.

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

.

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

.

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

Приложение ж

(рекомендуемое)

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

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

,

сначала нужно привести к форме

,

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

,

где - единичная матрица. Обозначая в последнем равенстве (в компонентном виде ) и ( ), приводим исходную систему к требуемой форме.

Можно поступить по-другому. Каждое из уравнений системы

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

,

Таким образом,

, .

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

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

или, в компонентном виде,

.

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

; ; .

Согласованные с ними нормы в пространстве матриц:

; ; ,

где - наибольшее собственное значение матрицы .

Теорема. Если , то система линейных алгебраических уравнений

(ж.1)

имеет единственное решение при любом векторе свободных членов и итерационный процесс

(ж.2)

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

Доказательство. Пусть - решение системы, т.е.

.

Отсюда с помощью неравенства треугольника получаем

или

.

Так как по условию теоремы , то

.

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

Пусть - вектор погрешности на -ой итерации. Вычитая (ж.2) из (ж.1), получим

или

,

где - -ая степень матрицы , - начальная погрешность. Отсюда

.

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

Замечание. Пусть - -ая компонента вектора погрешности . Так как , то и все компоненты вектора при стремятся к нулю с той же скоростью.

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

1) ;

2) ;

3) .