Участник:Василий Ломакин/Решение переопределенной СЛАУ
Материал из MachineLearning.
Содержание |
Постановка задачи
Рассмотрим прямоугольную матрицу размером :
Пусть в матрице число строк превышает число столбцов (), причём все строки линейно независимы. Систему уравнений вида
,
где А - описанная выше, — вектор-столбец решения, — вектор-столбец правой части, назовём переопределённой. Как можно видеть, в такой системе число уравнений превышает число неизвестных, и для неё не существует "классического" решения, например методом Гаусса.
Изложение метода
Приведем простой пример получения переопределённой системы линейных уравнений. Такого рода задачи часто встречаются, например, при обработке результатов экспериментов. Пусть — линейная (или близкая к линейной) функция аргумента . В точках известны значения функции . Тогда — коэффициенты, которые необходимо подобрать так, чтобы выполнялись условия . Получим систему пяти уравнений относительно двух неизвестных. Это — переопределённая система. Она не имеет классического решения, так как в общем случае не существует прямой, проходящей через все 5 точек (это возможно только тогда, когда какие - либо три уравнения полученной системы линейными преобразованиями сводятся к двум другим — система линейно зависима). Необходимо провести аппроксимирующую кривую, которая не проходит через экспериментальные точки, но в то же время отражает экспериментальную зависимость, сглаживает возможные выбросы за счёт погрешности эксперимента.
Рассмотрим более общий случай. Пусть коэффициенты необходимо определить по результатам измерения. Для каждого уравнения рассмотрим невязку - разность левой и правой части. Невязка может принимать положительные и отрицательные значения. Чтобы не учитывать знаки, применим возведение в квадрат. Введем функцию, равную сумме квадратов невязок
Примем за обобщённое решение переопределённой СЛАУ такие , для которых принимает наименьшие значение. Для определения обобщенного решения из условия минимума суммы квадратов невязки получаем систему двух уравнений, уже имеющую классическое решение:
Рассмотрим теперь общий случай. Определим невязку в виде
где — некоторые функции, образующие базис, например, тригонометрические: . Выражение называется обобщенным полиномом. В приведенном выше примере в качестве базисных функций были выбраны степенные функции . Обобщенный полином превратился в алгебраический.
В случае выбора произвольной системы базисных функций переопределенная СЛАУ и функционал будут иметь вид
Отыщем обобщенное решение методом наименьших квадратов: приравняем все частные производные по компонентам обобщенного решения к нулю (условия минимума) и изменяя порядок суммирования, получаем СЛАУ:
или, в виде системы уравнений:
Система метода наименьших квадратов имеет вид с матрицей , элементами которой являются скалярные произведения . Это — матрица Грамма. Ее свойства известны из курса линейной алгебры, эта матрица симметричная и положительно определенная. Таким образом, решение исследуемой СЛАУ существует и единственно. В правой части системы стоят проекции свободного члена исходной задачи на подпространство базисных функций .
Здесь учтено, что .
Анализ метода и оценка ошибок
Числовой пример
Список литературы
- Н.Н.Калиткин. Численные методы М.: Наука, 1978.
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.