МЕТОД БАЛОНИНА-ХОЛЕЦКОГО


Смотрите также: chol, rank, lsm

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


Опережающий расчет диагонали открывает возможности выбора ведущего элемента в схемах с перестановкой строк и столбцов, однако для планирования перестановок у нас есть еще более лакомая приманка. Как и в обычном методе Холецкого, матрицу P можно расширить вектором правой части системы нормальных уравнений MNK, т.е. обрабатывать [P,r]' (вместо P).

Квадраты элементов модифицируемого вектора правой части r на шаге алгоритма отвечает падениям квадрата нормы невязки ε=b–Ax при увеличении количества отличных от нуля элементов вектора x. Опережающий расчет как диагонали, так и этого вектора снабжает задачу выбора ведущего элемента двумя важнейшими информационными признаками: эффективностью падения основного критерия МНК и показателем точности вычислений (делителем).

В алгоритме ниже в качестве элемента r[k]=r[k]/s (квадрат этого числа отвечает падению показателя МНК на шаге) перестановками строк и столбцов с номерами от k до n можно подбирать максимальное по абсолютной величине отношение, для которого делитель s=L[k][k] вызывает доверие, т.е. s не является слишком малым для машинной арифметики числом.

Если максимальная невязка ε*=b–Ax при x=0 вычерпывается до завершения итераций, алгоритм приводит к трапециевидному разложению матрицы P=TT' неполного ранга rank(P)<n.


Rambler's Top100