Во многих приложениях возникает необходимость решения преопределенных систем уравнения, т.е. таких, в которых число уравнений m больше числа неизвестных n. Система уравнений имеет ранг не выше n, и точное решение невозможно, поэтому ищут решение, удовлетворяющее некоторому критерию качества, причем такое решение, как правило, не является точным решением системы. Наиболее широко используется критерий минимума суммы квадратов невязок , являющихся элементами вектора невязок R=AX-B размерности m.
Подход к решению переопределенных систем на основе минимизации суммы квадратов невязок получил собирательное название метода наименьших квадратов
Пусть решение соответствует минимуму суммы квадратов невязок
т.е достигает минимума. Такое решение называют нормальным псевдорешением.
Найдем , приравнивания нулю производную по x. При этом необходимо использовать правила дифференцирования векторов и матриц и следующие свойства операции транспонирования:
где a – скаляр;A,B, - матрицы или векторы.
В результате преобразований получим:
Полученная система уравнений
называется нормальной системой уравнений. Матрица является нормальной симметричной неотрицательно неопределенной, причем .
Нормальная система уравнений может быть решена любым прямым методом. Следует иметь ввиду, что необходимо выполнить большое число операций при перемножении матриц и последующем решении, это может привести к заметному росту ошибок округления.
Для решения предопределенных систем ранга n могут быть использованы численно более устойчивые методы ортогональных вращений и отражений. Алгоритмы решения соответствуют описанным выше алгоритмам для систем полного ранга, однако ортогональные матрицы имеют размерность m x m.
Для использования, например, метода вращения, достаточно в приведенном выше алгоритме перебор по i осуществлять до последний m-й строки матрицы A, а перебор столбцов выполнить для всех столбцов, т.е. для k = 1,2,…,n.
Отметим без доказательства, что в результате решения предопределенных систем методом вращений или отражений получается нормальное произведение.