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

Метод Гаусса

Большинство прямых методов решения СЛАУ в той или иной мере наследуют идею алгоритма последовательного исключения неизвестных – метода Гаусса. Если матрица задачи, например, является верхней треугольной, то произвольное k-ое уравнение системы имеет вид , ,  (3)

Последнее уравнение системы содержит всего лишь одно неизвестное , и его значение вычисляется первым:  (4)

Остальные неизвестные вычисляются последовательно по явным формулам

 (5)                           

Аналогичный алгоритм м.б. построен для задачи с нижней треугольной матрицей.

Суть метода Гаусса состоит в приведении матрицы задачи к верхнему (нижнему) треугольному виду. Для этих целей используются тождественные преобразования системы. В частности, решение задачи не меняется при замене произвольной строки системы на линейную комбинацию данной строки и произвольного числа других строк системы. Используя такого рода преобразования, можно последовательно, столбец за столбцом, исключить переменные, находящиеся ниже главной диагонали системы ЛАУ. Элементарный шаг такого преобразования можно выразить с помощью операции умножения л. и пр. части системы на элементарную нижнюю треугольную матрицу вида:

                                                      (6)

Матрицы  отличаются от единичной тем, что -ый столбец данной матрицы, начиная с элемента , и ниже , , формируется специальным образом (6) из соответствующих значений элементов преобразуемой матрицы. В результате умножения  (7) преобразованная матрица  будет иметь нулевые значения элементов первого столбца ниже главной диагонали:  Далее, на основе элементов матриц ,  последовательно формируются матрицы  и находятся , , …  (8)

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

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

Решение полученной системы уравнений находится с помощью алгоритма (4), (5).

Процедуру (7) – (9) принято называть прямым ходом метода Гаусса, а (4), (5) – соответственно обратный ход.

 

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

Одна операция умножения  имеет выч-ю сложность порядка .

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

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

Метод Гаусса является самым универсальным в своем классе и может быть использован для решения произвольных СЛАУ с невырожденной матрицей. Тем не менее, источником проблем являются нулевые (близкие к нулю) значения диагональных элементов, присутствующие в матрице изначально, либо появляющиеся  в процессе исключения неизвестных. Как видно из выражения (6), при формировании матриц  выполняется деление на , что в случае  приводит к потере корректности алгоритма. Для устранения этих проблем используется алгоритмы перестановок столбцов (строк) матрицы.

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

 

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

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

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

 

Сеточная область

Для построения разностной схемы необходимо построить сетку G_h - конечное множество точек, принадлежащих G, плотность распределения которых характеризуется параметрами h-шагом сетки. Пусть область изменения аргумента x есть отрезок G={0≤x≤1}. Разобьем этот отрезок точками x_i=i∙h, i=0,n на n равных частей длины h=1/n каждая. Множество точек x_i=i∙h, называется равномерной сеткой на отрезке 0≤x≤1 и обозначим ={x_i=i∙h, i=0,n}, а число h - расстояние между точками (узлами) сетки называется шагом сетки.

Разбиение отрезка 0≤x≤1 точками x_i, i=0,n можно производить произвольным образом: 0<x₁<…<x_n-1<1. Тогда получаем сетку ={x_i, i=0,n, x₀=0, x_n=1} c шагами h_i=x_i-x_i-1, которые зависит от номера узла сетки. Если h_i≠h_i+1 хотя бы в одной точке, то сетка называется неравномерной и такую сетку обозначают ŵ . Точки x₀ и x_n назовем граничными узлами и обозначим их г_h. Остальные узлы назовем внутренними и обозначим их w_h. Узлы, соседние с граничащими, назовем приграничными. Тогда имеем =w_h г_h.

Метод Ньютона

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

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

в предположении, что  – непрерывно-дифференцируемые функции.

Полагая , перейдём к векторной записи  (2)

Опишем общий шаг метода.

Пусть уже получено приближение  Разложим функцию  в ряд Тейлора, оставив только два первых члена в силу малости отклонения приближения  от корня: , – матрица Якоби для .

Очередное приближение  определяется как решение линейной системы , т.е.

Если матрица Якоби  не вырождена, то решение системы линейной системы можно записать в явном виде, что приводит к стандартной формуле метода Ньютона  (3)

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

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

 – система линейных уравнений.

 

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

Пусть в  выбрана нек-я векторная  и согласованная с ней матричная .

 

Теорема (о сходимости). Пусть

1) вектор-функция  определена и непрерывно-дифференцируема в области  где  – решение уравнения (2),

2) для всех  существует обратная матрица , причём

3) для всех

4)

Тогда метод Ньютона (3)

1)

2)

3)

Замечание. Оценка погрешности метода Ньютона:

Метод Гаусса

Большинство прямых методов решения СЛАУ в той или иной мере наследуют идею алгоритма последовательного исключения неизвестных – метода Гаусса. Если матрица задачи, например, является верхней треугольной, то произвольное k-ое уравнение системы имеет вид , ,  (3)

Последнее уравнение системы содержит всего лишь одно неизвестное , и его значение вычисляется первым:  (4)

Остальные неизвестные вычисляются последовательно по явным формулам

 (5)                           

Аналогичный алгоритм м.б. построен для задачи с нижней треугольной матрицей.

Суть метода Гаусса состоит в приведении матрицы задачи к верхнему (нижнему) треугольному виду. Для этих целей используются тождественные преобразования системы. В частности, решение задачи не меняется при замене произвольной строки системы на линейную комбинацию данной строки и произвольного числа других строк системы. Используя такого рода преобразования, можно последовательно, столбец за столбцом, исключить переменные, находящиеся ниже главной диагонали системы ЛАУ. Элементарный шаг такого преобразования можно выразить с помощью операции умножения л. и пр. части системы на элементарную нижнюю треугольную матрицу вида:

                                                      (6)

Матрицы  отличаются от единичной тем, что -ый столбец данной матрицы, начиная с элемента , и ниже , , формируется специальным образом (6) из соответствующих значений элементов преобразуемой матрицы. В результате умножения  (7) преобразованная матрица  будет иметь нулевые значения элементов первого столбца ниже главной диагонали:  Далее, на основе элементов матриц ,  последовательно формируются матрицы  и находятся , , …  (8)

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

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

Решение полученной системы уравнений находится с помощью алгоритма (4), (5).

Процедуру (7) – (9) принято называть прямым ходом метода Гаусса, а (4), (5) – соответственно обратный ход.

 

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

Одна операция умножения  имеет выч-ю сложность порядка .

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

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

Метод Гаусса является самым универсальным в своем классе и может быть использован для решения произвольных СЛАУ с невырожденной матрицей. Тем не менее, источником проблем являются нулевые (близкие к нулю) значения диагональных элементов, присутствующие в матрице изначально, либо появляющиеся  в процессе исключения неизвестных. Как видно из выражения (6), при формировании матриц  выполняется деление на , что в случае  приводит к потере корректности алгоритма. Для устранения этих проблем используется алгоритмы перестановок столбцов (строк) матрицы.

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

При перестановке строк СЛАУ решение задачи не изменяться. Данное свойство лежит в основе алгоритмов упорядочения строк матрицы.

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

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

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

- Матрица перестановок является унитарной матрицей: .

- Произведение любого числа матриц перестановок является матрицей перестановок.

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

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

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

. Тогда ,  

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

Замечание 1. Кроме рассмотренного алгоритма частичного упорядочения с выбором главного элемента по столбцам существуют аналогичные варианты упорядочения по строкам, а также по строкам и столбцам одновременно.

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

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