Материал из MachineLearning.
< Участник:Василий Ломакин(Различия между версиями)
|
м |
| (1 промежуточная версия не показана) |
| Строка 61: |
Строка 61: |
| | == См. также == | | == См. также == |
| | * [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]] | | * [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]] |
| | + | * [[Метод наименьших квадратов|Метод наименьших квадратов]] |
Текущая версия
Постановка задачи
Рассмотрим прямоугольную матрицу размером 
:
.
)
Пусть в матрице число строк превышает число столбцов (
), причём все строки линейно независимы.
Систему уравнений вида
( 1 )
,
где 
- описанная выше, 
— вектор-столбец решения, 
— вектор-столбец правой части, назовём переопределённой. Как можно видеть, в такой системе число уравнений превышает число неизвестных, и для неё не существует "классического" решения.
Изложение метода
Приведем простой пример получения переопределённой системы линейных уравнений. Такого рода задачи часто встречаются, например, при обработке результатов экспериментов. Пусть 
— линейная (или близкая к линейной) функция аргумента  = u_1x + u_0)
. В точках 
известны значения функции )
. Тогда 
— коэффициенты, которые необходимо подобрать так, чтобы выполнялись условия )
. Получим систему пяти уравнений относительно двух неизвестных. Это — переопределённая система. Она не имеет классического решения, так как в общем случае не существует прямой, проходящей через все 5 точек (это возможно только тогда, когда какие - либо три уравнения полученной системы линейными преобразованиями сводятся к двум другим — система линейно зависима). Необходимо провести аппроксимирующую кривую, которая не проходит через экспериментальные точки, но в то же время отражает экспериментальную зависимость, сглаживает возможные выбросы за счёт погрешности эксперимента.
Рассмотрим более общий случай. Пусть коэффициенты 
необходимо определить по результатам 
измерения. Для каждого уравнения рассмотрим невязку 
- разность левой и правой части. Невязка может принимать положительные и отрицательные значения. Чтобы не учитывать знаки, применим возведение в квадрат. Введем функцию, равную сумме квадратов невязок:
( 2 )
 = \sum\limits_{k = 0}^n {r_k^2} = \sum\limits_{k = 0}^n {(u_1 x_k + u_0 - f_k)^2})
Примем за обобщённое решение переопределённой СЛАУ такие , для которых )
принимает наименьшие значение. Для определения обобщённого решения из условия минимума суммы квадратов невязки получаем систему двух уравнений, уже имеющую классическое решение:
Рассмотрим теперь общий случай. Определим невязку 
в виде
} - f(x_k),\ k = 1, \ldots, n,)
где )
— некоторые функции, образующие базис, например, тригонометрические:  = \sin (jx))
. Выражение })
называется обобщённым полиномом. В приведенном выше примере в качестве базисных функций были выбраны степенные функции  = x^j)
. Обобщённый полином превратился в алгебраический.
В случае выбора произвольной системы базисных функций переопределенная СЛАУ и функционал )
будут иметь вид
 + \ldots + u_p \varphi_p(x_0) = f_0, \\ \ldots \\ u_0 \varphi_0 (x_n) + \ldots + u_p\varphi_p (x_n) = f_n,\\ \Phi (u_0,\ldots,u_n) = \sum\limits_{i = 0}^n (\sum\limits_{j = 0}^p u_j \varphi_j(x_i) - f_i)^2 \end{gather*})
Отыщем обобщенное решение методом наименьших квадратов: приравняем все частные производные по компонентам обобщенного решения к нулю (условия минимума):
\left({\sum\limits_{j = 0}^p {u_j\varphi_j (x_i) - f_i}} \right)}=0)
и изменяя порядок суммирования, получаем СЛАУ:
\varphi_k (x_i)}}\right)u_j = \sum\limits_{i = 0}^n {f_i\varphi_k (x_i)}},\ k = 0, \ldots, p,)
или, в виде системы уравнений:
 u_0 + (\varphi_0, \varphi_1)u_1 + \ldots + (\varphi_0, \varphi_p)u_p = (\varphi_0, f), \\ (\varphi_1, \varphi_0) u_0 + (\varphi_1, \varphi_1)u_1 + \ldots + (\varphi_1, \varphi_p)u_p = (\varphi_1, f), \\ \ldots \\ (\varphi_p, \varphi_0) u_0 + (\varphi_p, \varphi_1)u_1 + \ldots + (\varphi_p, \varphi_p)u_p = (\varphi_p, f), \end{gather*})
Система метода наименьших квадратов имеет вид 
с матрицей 
, элементами которой являются скалярные произведения  = \sum\limits_{i = 0}^n \varphi_j (x) \varphi_k (x_i))
:
 & (\varphi_0,\ \varphi_1) & \ldots & (\varphi_0,\ \varphi_p)\\
(\varphi_1,\ \varphi_0) & (\varphi_1,\ \varphi_1) & \ldots & (\varphi_1,\ \varphi_p)\\
\ldots & \ldots & \ldots & \ldots\\
(\varphi_p,\ \varphi_0) & (\varphi_p,\ \varphi_1) & \ldots & (\varphi_p,\ \varphi_p)\\
\end{vmatrix}.
)
Это — матрица Грама. В правой части системы стоят проекции свободного члена исходной задачи на подпространство базисных функций  = \sum\limits_{i = 0}^n {\varphi_j(x_i)f_i})
. Матрица симметричная и положительно определенная, таким образом, решение исследуемой СЛАУ существует и единственно. Находится, например, с помощью итерационного метода Гаусса.
Советы программисту
Отметим основные свойства матрицы Грама, полезные при программировании:
- Матрица симметрична, что позволяет сократить объём вычислений при заполнении матрицы.
- Матрица является положительно определённой, следовательно, при решении системы нормальных уравнений методом исключения Гаусса можно отказаться от процедуры выбора главного элемента.
- Определитель матрицы будет отличен от нуля, если в качестве базиса выбраны линейно независимые функции, при этом система имеет единственное решение.
- При обработке экспериментальных данных, определённых с погрешностью
в каждой точке, обычно сначала берут небольшое (одну-две) число базисных функций. После вычисления приближённого решения, вычисляют сумму квадратов невязок по формуле, аналогичной (2). Если получается, что 
, то необходимо расширить базис добавлением новых функций. Расширение базиса необходимо производить до тех пор, пока не выполнится условие 
.
- Выбор конкретных базисных функций зависит от свойств функции , таких как периодичность, экспоненциальный или логарифмический характер, свойства симметрии, наличие асимптотики и т.д.
Список литературы
- А.Е.Мудров Численные методы для ПЭВМ. Томск: Раско, 1991.
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
См. также
