Ю11.16

Задача:
Для заданной матрицы [latex]A(n, n)[/latex] найти обратную [latex]A^{-1}[/latex], используя итерационную формулу:
[latex]A_{k}^{-1} = A_{k-1}^{-1}(2E-A A_{k}^{-1}),[/latex] где [latex]E[/latex] — единичная матрица, [latex]A_{0}^{-1} = E[/latex]. Итерационный процесс заканчивается, если для заданной погрешности [latex]\varepsilon[/latex] справедливо:
[latex]\left| det(A A_{k}^{-1})-1 \right| \le \varepsilon[/latex]

Анализ задачи:
Прежде чем приступать к решению средствами языка C++, я создал прототип в системе компьютерной алгебры Wolfram Mathematica, с которым планировал сверяться при тестировании программы. Тем не менее, внимательный анализ показал, что с таким выбором начального приближения процесс уже на пятом шаге в значительной мере расходится даже для матриц размера 2*2. После уточнения условий и анализа дополнительного материала, посвященного методу Ньютона-Шульца, исходное приближение было изменено (по результатам исследования «An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications», Victor Pan, Robert Schreiber, стр. 8):
[latex]A_{0}^{-1} =\frac { A }{ \left\| A \right\|_{1} \left\| A \right\| _{\infty } }[/latex], где [latex]{ \left\| A \right\| }_{ 1 }=\max _{ i }{ \sum _{ j=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } } [/latex], [latex]{ \left\| A \right\| }_{ \infty }=\max _{ j }{ \sum _{ i=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } }[/latex].
Эффективность предложенного подхода иллюстрируют результаты работы прототипа:
процесс сходится
Следовательно, из пространства задачи можно переместиться в пространство решения и составить алгоритм реализации предложенного метода на языке C++.

Тесты:

[latex]n[/latex] [latex]A[/latex] [latex]A^{-1}[/latex] Результат
3 1 2 3
5 5 7
11 13 7
-0.964771 0.430661 -0.017183
0.723533 -0.447973 0.137884
0.172358 0.155200 -0.086211
Пройден
2 1 2
2 1
-0.333067 0.666400
0.666400 -0.333067
Пройден
5 1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
Пройден
3 1 2 3
4 5 6
7 8 9
Матрица вырождена Пройден

Программный код:

Программа доступна для тестирования по ссылке: http://ideone.com/7YphoX.

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

  1. Инициализация динамического двухмерного массива и передача его в функцию.
  2. Вычисление определителя матрицы (с применением метода Гаусса).
  3. Вычисление нормы матрицы.
  4. Транспонирование матрицы.
  5. Умножение матрицы на скаляр.
  6. Матричное умножение матриц.
  7. Сложение двух матриц.
  8. Непосредственно итерационный процесс Ньютона-Шульца

Ниже приведено пояснение к подходу к реализации некоторых подзадач:

  • Выделение памяти для хранения массива происходит не на этапе запуска программы, после компиляции. Для инициализации использован конструктор new
  • Вычисление определителя можно разбить на два последовательных шага:
    1. Приведение матрицы к верхнетреугольному виду (методом Гаусса).
    2. Вычисление определителя как произведения элементов главной диагонали.
    3. Если матрица вырождена, то дальнейшие вычисления не производятся.

  • Нормы матрицы вычисляются как максимальные значения суммы элементов по столбцам и строкам соответственно.
  • При транспонировании обмениваются местами элементы, симметричные главной диагонали.
  • При умножении матрицы на скаляр каждый элемент матрицы умножается на соответствующее вещественное число.
  • При перемножении двух квадратных матриц используется промежуточный массив для хранения результата вычислений.
  • Сложение двух матриц аналогично попарному сложению элементов, расположенных на соответствующих позициях.
  • Максимально допустимая погрешность для метода Ньютона-Шульца [latex]\varepsilon = 0.001[/latex]. Программа использует локальный массив для хранения [latex]A_{k}^{-1}[/latex], инициализация которого происходит в теле цикла.

Технические детали реализации:
При выполнении подзадач часто приходится использовать локальные массивы, так что для очистки выделенной под них памяти создана отдельная функция clear().

Related Images: