Начало
Учебные материалы
Метод преобразования
Идея метода преобразования Предварительная сортировка Метод исключения Гаусса Пирамиды и пирамидальная сортировка Схема Горнера Приведение задачи
Метод исключения Гаусса
`{ (a_{11}x + a_{12} y = b_1),(a_{21}x + a_{22} y = b_2) :}`
Стандартный метод поиска этого решения состоит в использовании одного из уравнений для
того, чтобы выразить одну переменную как функцию другой, а затем подставить
результат в другое уравнение. Это дает линейное уравнение относительно одной
переменной, решение которого позволяет найти значение второй переменной.
Решить систему из `n` уравнений можно, обобщив метод подстановки, примененный для решения системы из двух линейных уравнений,
но полученный в результате алгоритм будет слишком громоздким.
--
Идея *метода исключения Гаусса* заключается в преобразовании системы `n` линейных
уравнений с `n` неизвестными в эквивалентную систему (т.е. систему с тем же
решением, что и у исходной) с верхнетреугольной матрицей коэффициентов, т.е. такой,
у которой все элементы ниже главной диагонали равны нулю:
`{(a_{11}x_1+...+a_{1n}x_n=b_1),(vdots),(a_{n1}x_1+...+a_{n n}x_n=b_n) :} => {(a'_{11}x_1+,a'_{12}x_2+...+,a'_{1n}x_n=b'_1),(,a'_{22}x_2+...+,a'_{2n}x_n=b'_2),(,,vdots),(,,a'_{n n}x_n=b'_n) :}`
--
Cистему линейных уравнений с верхнетреугольной матрицей легко
решить методом обратной подстановки следующим образом. Сначала мы
вычисляем значение `x_n` из последнего уравнения; затем подставляем полученное
значение в предпоследнее уравнение и получаем значение `x_{n-1}`. Продолжая
выполнять подстановки вычисленных значений переменных в очередные уравнения,
мы получим значения всех `n` переменных — от `x_n` до `x_1`.
--
Получить из системы линейных уравнений с произвольной матрицей коэффициентов `A` эквивалентную систему линейных
уравнений с верхнетреугольной матрицей `A'` можно с помощью следующих операций:
* обмена двух уравнений системы линейных уравнений;
* умножения уравнения на ненулевую величину;
* замены уравнения на сумму или разность этого уравнения и другого
уравнения, умноженного на некоторую величину.
Ни одна из элементарных операций не изменяет решение системы
линейных уравнений, любая система линейных уравнений, полученная из
исходной при помощи серии элементарных операций, будет иметь то же решение, что
и исходная система линейных уравнений.
--
Сначала используем в качестве опорного элемента `a_{11}` для того, чтобы сделать все коэффициенты при
`x_1` в строках ниже первой нулевыми.
В частности, заменим второе уравнение разностью между ним и первым уравнением, умноженным на `a_{21}//a_{11}` для того, чтобы
получить нулевой коэффициент при `x_1`. Аналогичные действия для остальных строк.
Затем обнулим все коэффициенты при `x_i` в уравнениях ниже второго,
вычитая из каждого из этих уравнений второе, умноженное на соответствующий
коэффициент. Повторяя эти действия для каждой из первых `n-1`
строк, получим систему линейных уравнений с верхнетреугольной матрицей коэффициентов.
--
Алгоритм GaussElimination (`A, b`)
// Входные данные: Матрица `A[1...n, 1...n+1]`
// свободные члены `b_i` в столбце `n+1`
// Выходные данные: Эквивалентная верхнетреугольная матрица
// на месте матрицы `A`
**for** `i in [1...n-1]` **do**
`quad` **for** `j in [i+1...n]` **do**
`quad quad t larr A[j, i]//A[i, i]`
`quad quad` **for** `k in [i...n+1]` **do**
`quad quad quad quad A[j, k] larr A[j, k] - A[i, k] * t`
--
Если `A[i, i] =0`, нельзя выполнить деление на этот элемент и, следовательно, использовать `i`-ую строку в качестве опорной
на `i`-ой итерации алгоритма. В этом случае мы должны воспользоваться
первой из элементарных операций и обменять `i`-ую строку с одной из строк ниже
ее, у которой в `i`-ом столбце находится ненулевой элемент. Для уменьшения ошибки вычислений
рекомендуется выбирать строку с наибольшим
абсолютным значением коэффициента в `i`-ом столбце для обмена с `i`-ой строкой, а затем
использовать ее в качестве опорной на `i`-ой итерации.
--
Наиболее глубоко вложенный цикл состоит из одной строки:
`A[j, k] larr A[j, k] - A[i, k] * t`
Умножение является базовой операцией данного алгоритма.
`C(n)=sum_{i=1}^{n-1} sum_{j=i+1}^{n} sum_{k=i}^{n+1} 1= sum_{i=1}^{n-1} sum_{j=i+1}^{n} (n+2-i)=`
`=sum_{i=1}^{n-1} (n+2-i)(n-i)=sum_{i=1}^{n-1} (i+2)i=sum_{i=1}^{n-1} i^2+sum_{i=1}^{n-1} 2i=`
`=((n-1)n(2n-1))/6+2((n-1)n)/2~~ (n^3)/3 in Theta(n^3)`
Поскольку временная эффективность обратной подстановки
в алгоритма исключения Гаусса равна `Theta(n^2)`, общее время работы алгоритма определяется
кубическим временем стадии исключения, так что алгоритм Гаусса — кубический.
--
Метод исключения Гаусса имеет интересный и очень полезный побочный
результат, именуемый `LU`-разложением, или `LU`-декомпозицией матрицы коэффициентов.
Верхнетреугольная матрица `U` представляет собой результат исключения,
а нижнетреугольную матрицу `L` образована единицами на главной
диагонали и множителями, вычисляемыми в процессе исключения Гаусса для
обнуления соответствующих коэффициентов в строках матрицы.
--
Произведение `LU` этих матриц равно исходной матрице `А`.
Следовательно, решение системы линейных уравнений `Ax=b` эквивалентно
решению системы `LUx = b`. Решить ее можно следующим образом. Обозначим
`y = Ux`, тогда `Ly = b`.
Сначала решим систему `Ly =b`, что очень просто сделать,
поскольку `L` — нижнетреугольная матрица.
Затем решим систему `Ux = y`, что опять же несложно, поскольку `U` — верхнетреугольная матрица.
Таким образом, с помощью `LU`-разложения матрицы `A`, мы можем решать системы
линейных уравнений `Ax = b` для разных векторов свободных членов `b` за `Theta(n^2)`.
--
Обратная к матрице `A` размером `n xx n` матрица
также имеет размер `n xx n` и обозначается как `A^{-1}`:
`A*A^{-1}=I`,
где `I` — единичная матрица размером `n xx n`.
Для нахождения обратной матрицы нужно найти `n^2` чисел `x_{ij}`, таких что
`[(a_{11},...,a_{1n}),(vdots,ddots,vdots),(a_{n1},...,a_{n n})] [(x_{11},...,x_{1n}),(vdots,ddots,vdots),(x_{n1},...,x_{n n})]=[(1,0,...,0,0),(vdots,,ddots,,vdots),(0,0,...,0,1)]`
--
Мы можем найти неизвестные числа, решая `n` систем линейных уравнений с одной и той же матрицей коэффициентов `A`,
у которых вектор неизвестных `x^j`
представляет собой `j`-ый столбец обратной матрицы, а вектор свободных членов
`e^j` — `j`-ый столбец единичной матрицы:
`A*x^j=e^j`
Так как каждое решение можно найти за `Theta(n^2)`, то общее время для нахождения обратной матрицы равно `Theta(n^3)`.
--
Метод исключения Гаусса помогает и при вычислении определителя.
Определитель верхнетреугольной матрицы равен произведению ее элементов на главной диагонали,
а элементарные операции, выполняемые алгоритмом исключения Гаусса либо оставляют его значение неизменным,
либо меняют знак, либо приводят к умножению его на константу. В результате мы можем вычислить
определитель матрицы за кубическое время.
