Метод оптимального исключения

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

(4.10)

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

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

, .

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

, .

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

Метод Гаусса с выбором главного элемента

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

а) метод Гаусса с выбором главного элемента по строке: в системе на каждом шаге исключения проводится соответствующая перенумерация переменных;

б) метод Гаусса с выбором главного элемента по столбцу: на каждом шаге исключения проводится перенумерация уравнений;

в) метод Гаусса с выбором главного элемента во всей матрице системы: в этом случае проводится перенумерация и переменных и уравнений.

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

ЛЕКЦИЯ № 9

Методы, основанные на разложении матриц

Схема Холецкого

Используем для решения системы (4.1) теорему о разложении невырожденной квадратной матрицы в произведение нижней и верхней треугольных матриц.

Теорема 4.1.Если главные миноры матрицы отличны от нуля:

, , …, ,

то матрица представима в виде

, (4.11)

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

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

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

(4.12)

Учитывая разложение (4.11), система (4.1) принимает вид . Тогда вектор неизвестных можно найти из цепочки матричных уравнений

, (4.13)

Вектор находится из системы с нижней треугольной матрицей

по формулам , , . Определив вектор , находим

вектор неизвестных из системы с верхней треугольной матрицей

Вычисление проводится по формулам, аналогичным формулам для обратного хода схемы единственного деления Гаусса

, , .

Описанный метод решения систем линейных алгебраических уравнений называется схемой Холецкого.

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

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

Будем искать разложение действительной матрицы системы (4.1) в виде

, (4.14)

где

- диагональная матрица с элементами .

После перемножения матриц получаем

, ,

, .

Потребуем, чтобы элементы были положительными числами. Тогда получим

(4.15)

Таким образом, разложение (4.14) существует и определяется формулами (2.15). Тогда решение системы (4.1) сводится к решению двух систем с треугольными матрицами

, .

Первая система имеет вид

и ее решение находится по формулам

, , .

Вторая система

дает решение исходной системы (4.1)

, , .

Если матрица является положительно определенной (все главные миноры положительны), то и . Формулы разложения имеют в этом случае вид

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

ЛЕКЦИЯ № 10

Метод отражений

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

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

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

Вектор строится по правилу

, (4.16)

где , , .

Будем преобразовывать расширенную матрицу систему по правилу

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

Пусть уже построена матрица , у которой , , . Теперь в качестве и берутся вектора

, ,

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

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

, ,

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

Пример.

Решить систему линейных алгебраических уравнений методом отражений

Решение: По системе уравнений составим матрицу

Шаг 1. , , , ,

, , ,

Тогда .

Шаг 2. , , , ,

, , ,

Тогда .

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

Метод вращений

Вещественные унитарные матрицы

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

, . (4.17)

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

, , (4.18)

если , и , в противном случае.

Теорема 4.3.Любая действительная матрица преобразуется в верхнюю треугольную матрицу после умножения слева на конечную цепочку матриц простого поворота .

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

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