Метод Гаусса — Жордана
Перейти к навигации
Перейти к поиску
Метод Гаусса — Жордана (метод полного исключения неизвестных) — метод, который используется для решения квадратных систем линейных алгебраических уравнений, нахождения обратной матрицы, нахождения координат вектора в заданном базисе или отыскания ранга матрицы. Метод является модификацией метода Гаусса. Назван в честь К. Ф. Гаусса и немецкого геодезиста и математика Вильгельма Йордана[1].
Алгоритм
[править | править код]- Выбирают первый слева столбец матрицы, в котором есть хоть одно отличное от нуля значение.
- Если самое верхнее число в этом столбце ноль, то меняют всю первую строку матрицы с другой строкой матрицы, где в этой колонке нет нуля.
- Все элементы первой строки делят на верхний элемент выбранного столбца.
- Из оставшихся строк вычитают первую строку, умноженную на первый элемент соответствующей строки, с целью получить первым элементом каждой строки (кроме первой) ноль.
- Далее проводят такую же процедуру с матрицей, получающейся из исходной матрицы после вычёркивания первой строки и первого столбца.
- После повторения этой процедуры раз получают верхнюю треугольную матрицу
- Вычитают из предпоследней строки последнюю строку, умноженную на соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась только 1 на главной диагонали.
- Повторяют предыдущий шаг для последующих строк. В итоге получают единичную матрицу и решение на месте свободного вектора (с ним необходимо проводить все те же преобразования).
Расширенный алгоритм для нахождения обратной матрицы
[править | править код]Пусть дано:
Прямой ход (алгоритм образования нулей под главной диагональю)
[править | править код]- Разделим первую строку матрицы А на получим: , j — столбец матрицы А.
- Повторяем действия для матрицы I, по формуле: , s — столбец матрицы I
- Получим:
- Будем образовывать 0 в первом столбце :
- Повторяем действия для матрицы І, по формулам :
- Получим:
- продолжаем выполнять аналогичные операции, используя формулы :
- при условии, что
- Повторяем действия для матрицы І, по формулам :
- при условии, что
- Получим :
Обратный ход (алгоритм образования нулей над главной диагональю)
[править | править код]Используем формулу: , при условии, что
Повторяем действия для матрицы І, по формуле : , при условии, что
Окончательно получаем :
Пример
[править | править код]Для решения следующей системы уравнений:
Запишем её в виде матрицы 3×4, где последний столбец является свободным членом:
Проведём следующие действия:
- К строке 2 добавим: −4 × Строку 1.
- К строке 3 добавим: −9 × Строку 1.
Получим:
- К строке 3 добавим: −3 × Строку 2.
- Строку 2 делим на −2
- К строке 1 добавим: −1 × Строку 3.
- К строке 2 добавим: −3/2 × Строку 3.
- К строке 1 добавим: −1 × Строку 2.
В правом столбце получаем решение:
- .
Реализация алгоритма на языке программирования C#
[править | править код]namespace Gauss_Jordan_Method
{
class Maths
{
/// <summary>
/// Метод Гаусса-Жордана (Обратная матрица)
/// </summary>
/// <param name="Matrix">Начальная матрица</param>
/// <returns></returns>
public static double[,] GaussJordan(double[,] Matrix)
{
int n = Matrix.GetLength(0); //Размерность начальной матрицы
double[,] xirtaM = new double[n, n]; //Единичная матрица (искомая обратная матрица)
for (int i = 0; i < n; i++)
xirtaM[i, i] = 1;
double[,] Matrix_Big = new double[n, 2*n]; //Общая матрица, получаемая скреплением Начальной матрицы и единичной
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
Matrix_Big[i, j] = Matrix[i, j];
Matrix_Big[i, j + n] = xirtaM[i, j];
}
//Прямой ход (Зануление нижнего левого угла)
for (int k = 0; k < n; k++) //k-номер строки
{
for (int i = 0; i < 2*n; i++) //i-номер столбца
Matrix_Big[k, i] = Matrix_Big[k, i] / Matrix[k, k]; //Деление k-строки на первый член !=0 для преобразования его в единицу
for (int i = k + 1; i < n; i++) //i-номер следующей строки после k
{
double K = Matrix_Big[i, k] / Matrix_Big[k, k]; //Коэффициент
for (int j = 0; j < 2*n; j++) //j-номер столбца следующей строки после k
Matrix_Big[i, j] = Matrix_Big[i, j] - Matrix_Big[k, j] * K; //Зануление элементов матрицы ниже первого члена, преобразованного в единицу
}
for (int i = 0; i < n; i++) //Обновление, внесение изменений в начальную матрицу
for (int j = 0; j < n; j++)
Matrix[i, j] = Matrix_Big[i, j];
}
//Обратный ход (Зануление верхнего правого угла)
for (int k = n - 1; k > -1; k--) //k-номер строки
{
for (int i = 2*n - 1; i > -1; i--) //i-номер столбца
Matrix_Big[k, i] = Matrix_Big[k, i] / Matrix[k, k];
for (int i = k - 1; i > -1; i--) //i-номер следующей строки после k
{
double K = Matrix_Big[i, k] / Matrix_Big[k, k];
for (int j = 2*n - 1; j > -1; j--) //j-номер столбца следующей строки после k
Matrix_Big[i, j] = Matrix_Big[i, j] - Matrix_Big[k, j] * K;
}
}
//Отделяем от общей матрицы
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
xirtaM[i, j] = Matrix_Big[i, j + n];
return xirtaM;
}
}
}
Примечания
[править | править код]- ↑ Транскрипция фамилии Йордан как «Жордан» является ошибочной, но она общепринята и встречается в большинстве русскоязычных источников.
Литература
[править | править код]- Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (2nd ed.), New York: John Wiley & Sons, ISBN 978-0471624899.
- Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S. (2006), Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2nd ed.), Wiley-Interscience, ISBN 978-0-471-79156-0.
- Calinger, Ronald (1999), A Contextual History of Mathematics, Prentice Hall, ISBN 978-0-02-318285-3.
- Farebrother, R.W. (1988), Linear Least Squares Computations, STATISTICS: Textbooks and Monographs, Marcel Dekker, ISBN 978-0-8247-7661-9
- Higham, Nicholas (2002), Accuracy and Stability of Numerical Algorithms (2nd ed.), SIAM, ISBN 978-0-89871-521-7.
- Katz, Victor J. (2004), A History of Mathematics, Brief Version, Addison-Wesley, ISBN 978-0-321-16193-2.
- Lipson, Marc; Lipschutz, Seymour (2001), Schaum's outline of theory and problems of linear algebra, New York: McGraw-Hill, pp. 69—80, ISBN 978-0-07-136200-9.
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.2", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
Ссылки
[править | править код]- Algorithm for Gauss-Jordan elimination in Python (англ.)
- Kaw, Autar; Kalu, Egwu Numerical Methods with Applications: Chapter 04.06 Gaussian Elimination . University of South Florida (2010).
В статье есть список источников, но не хватает сносок. |