- •3.1. Основные определения
- •3.2. Действия с матрицами
- •3.2.2. Умножение матриц
- •3.3. Абсолютная величина и норма матрицы
- •4.2 Вычислительная устойчивость методов решения слау
- •4.3 Методы исключения
- •4.3.1 Схема единственного деления
- •4.3.2 Метод Жордана
- •4.3.3 Метод оптимального исключения
- •4.3.4 Метод Гаусса с выбором главного элемента
- •4.4 Методы, основанные на разложении матриц
- •4.4.1. Схема Холецкого
- •4.4.2 Метод квадратного корня
- •4.4.3 Метод отражений
- •4.4.4 Метод вращений
- •4.5 Методы, основанные на построении вспомогательной системы векторов
- •4.5.1 Метод ортогонализации
- •4.5.2 Метод сопряженных градиентов
3.3. Абсолютная величина и норма матрицы
Неравенство А ≤ В между матрицами А = [аij ] и B =[bij ] одинаковых типов обозначает, что аij ≤ bij . В этом смысле не всякие две матрицы сравнимы между собой.
Под абсолютной величиной (модулем) матрицы А= [аij ] будем понимать матрицу | А| = [| аij| ]
где | аij| — модули элементов матрицы А.
Если А и В— матрицы, для которых операции А + В и АВ имеют смысл, то:
а) | А + В | ≤ | А | + | В |;
б) | А В | ≤ | А | · | В |;
в) | α А | = | α | · | А |; ||||
(α — число).
Под нормой матрицы А = [аij ] понимается действительное число || A ||, удовлетворяющее условиям:
а) ||A|| ≥ 0, причем ||A]| =0 тогда и только тогда, когда A = 0;
б) || α А || = | α | · ||А ||( α — число) и, в частности, || - А || = ||А ||;
в) || А + В || ≤ || А || + || В ||;
г) || А В || ≤ || А || · || В ||;
(А и В — матрицы, для которых соответствующие операции имеют смысл).
В дальнейшем для матрицы А = [аij ] произвольного типа мы будем рассматривать главным образом три легко вычисляемые нормы;
1) || А || m = | аij| (т-норма);
2) || А || l = | аij| (l-норма);
3) || А || l = (k -норма).
ЛЕКЦИЯ № 7
МЕТОДЫ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ
АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
4.1 Классификация методов решения систем линейных
алгебраических уравнений
К решению систем линейных алгебраических уравнений сводится подавляющее большинство задач вычислительной математики. В настоящее время предложено огромное количество алгоритмов решения таких систем.
Все методы решения линейных алгебраических уравнений можно разделить на две большие группы: прямые и итерационные. В прямых (или точных) методах решение системы находится за конечное число арифметических действий. Итерационные методы позволяют найти за конечное число итераций приближенное решение системы с любой наперед заданной точностью .
Примером прямого метода решения СЛАУ служит метод Крамера, в соответствии с которым
, .
Однако на практике этот метод не используется, так как он требует выполнения очень большого количества арифметических операций. Большая часть существующих прямых методов укладывается в следующую схему. Пусть задана система
(4.1)
линейных алгебраических уравнений. Умножим обе части равенства (4.1) слева на такие матрицы , при которых новая система
(4.2)
равносильна исходной и легко решается. Для этого достаточно, чтобы матрица
была треугольной или диагональной. Методы, основанные на подобных преобразованиях, составляют в настоящее время самую значительную группу среди численных методов задач алгебры.
Одним из старейших является метод Гаусса, в основе которого лежит идея последовательного исключения неизвестных. Он использует левые треугольные матрицы и позволяет свести исходную систему уравнений к системе с правой треугольной матрицей. Этот метод легко реализуется на компьютере, его схема с выбором главного элемента позволяет решать системы с произвольной невырожденой матрицей, а компактная схема – получить результаты с повышенной точностью. Среди всех прямых методов метод Гаусса требует минимального объема вычислений.
Непосредственно к методу Гаусса примыкают метод Жордана и метод оптимального исключения. Эти методы используют треугольные матрицы (как левые, так и правые) и позволяют привести исходную систему к системе с диагональной матрицей. Метод оптимального исключения позволяет при заданном объеме оперативной памяти решать системы более высокого порядка, чем метод Жордана.
Перечисленные методы входят в группу методов исключения. Это название объясняется тем, что при каждом умножении на матрицу в матрице системы исключается один или несколько элементов. Существуют методы решения систем, которые сочетают в себе как свойства прямых методов, так и итерационных. Как итерационные они построены на минимизации некоторого функционала, достигающего своего минимума на решении системы (4.1). Однако итерации обрываются не позднее чем на -ом шаге ( - порядок системы), давая точный ответ. К таким методам относится метод сопряженных градиентов.