ВВЕДЕНИЕ


Существует ряд численных методов решения системы линейных алгебраических уравнений Ax=b: преобразованиями Гаусса-Жордана, разложением матрицы A на более простые составляющие, итерационными процедурами уточнения решения. Часть известных методов здесь кратко освещены, но упор все же сделан на более редко рассматриваемой ситуации, когда инвертировать матрицу нельзя. Минимизируя квадратичную норму разностей левой и правой частей, систему сводят к виду A'Ax=A'b, симметрическая неотрицательно определенная матрица P=A'A называется матрицей метода наименьших квадратов полученной системы нормальных уравнений Px=r, r=A'b. Такая система всегда совместна (разрешима). Нас интересуют нетривиальные ситуации, когда решение неединственно.

Разложение Холецкого. Для симметричных матриц P'=P относительно просто ищется разложение Холецкого P=LL', где L представляет собой нижнюю треугольную матрицу:

L=
  L11  
  0  
 ... 
  0  
 L21 
  L22  
 ... 
0
 ... 
 ... 
 ... 
 ... 
 Ln1 
 Ln2 
 ... 
  Lnn  


Решение уравнения. После разложений, уравнение Px=r заменяется на LL'x=r или USV'X=r и решается последовательной инверсией более простых сомножителей L (нижняя треугольная матрица), U,V (матрицы ортогональных столбцов), S (диагональная матрица), например, L'x=L–1r. Далее: x=(L')–1L–1r. Для систем с симметричной матрицей этот способ предпочтителен, поскольку учитывает симметрию.

Уже уравнение первого порядка ax=b подымает вопрос о том, что делать, при малом значении a. С одной стороны, на ноль (или малое в машинной арифметике число) в x=b/a делить нельзя. Если a, b малы, но сопоставимы, по своим значениям, то их можно отмасштабировать и перевести задачу в обычное ее русло. Если a, b пренебрежимо малы, это означает независимость значения x от уравнения связи. В таких случаях задачу нужно доопределять. Если пренебрежимо мало только a, это означает некорректность решаемой задачи.

Классический подход хорош своим быстродействием тогда, когда задача имеет однозначное решение. Метод Холецкого в чистом своем виде, часто публикуемом, не приспособлен для решения задач более общего характера просто потому, что в нем все отдано скорости счета в ущерб расчетам, позволяющим извлечь из данных информацию для выбора пути решения. В книге рассмотрим, как устроен указанный метод, а потом подыщем вариант модифицированного алгоритма, позволяющий учесть не учтенные в его реализации дополнительные аспекты.

КНИГА


Rambler's Top100