Участник:Василий Ломакин/Решение переопределенной СЛАУ

Материал из MachineLearning.

< Участник:Василий Ломакин

Версия от 14:36, 12 ноября 2008; Василий Ломакин (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

Содержание

1 Постановка задачи
2 Изложение метода
3 Анализ метода и оценка ошибок
4 Числовой пример
5 Список литературы
6 См. также

Постановка задачи

Рассмотрим прямоугольную матрицу размером :

$A= \left( \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n}\\ a_{21} & a_{22} & \ldots & a_{2n}\\ \ldots & \ldots & \ldots & \ldots \\ a_{m1} & a_{m2} & \ldots & a_{mn}\\ \end{array}\right).$

Пусть в матрице число строк превышает число столбцов ( $m > n$ ), причём все строки линейно независимы. Систему уравнений вида

( 1 )

$Au=f$ ,

где А - описанная выше, ${u}={\{u_1, \ldots , u_n \}}^T$ — вектор-столбец решения, ${f}={\{f_1, \ldots , f_n \}}^T$ — вектор-столбец правой части, назовём переопределённой. Как можно видеть, в такой системе число уравнений превышает число неизвестных, и для неё не существует "классического" решения, например методом Гаусса.

Изложение метода

Приведем простой пример получения переопределённой системы линейных уравнений. Такого рода задачи часто встречаются, например, при обработке результатов экспериментов. Пусть $f$ — линейная (или близкая к линейной) функция аргумента $x:\ f(x) = u_1x + u_0$ . В точках $x_k$ известны значения функции $f(x_k)$ . Тогда $u_0,\ u_1$ — коэффициенты, которые необходимо подобрать так, чтобы выполнялись условия $u_1x_k + u_0 = f_k,\ k = 0,1,2,3,4,\ f_k = f(x_k)$ . Получим систему пяти уравнений относительно двух неизвестных. Это — переопределённая система. Она не имеет классического решения, так как в общем случае не существует прямой, проходящей через все 5 точек (это возможно только тогда, когда какие - либо три уравнения полученной системы линейными преобразованиями сводятся к двум другим — система линейно зависима). Необходимо провести аппроксимирующую кривую, которая не проходит через экспериментальные точки, но в то же время отражает экспериментальную зависимость, сглаживает возможные выбросы за счёт погрешности эксперимента.

Рассмотрим более общий случай. Пусть коэффициенты ${u_0,\ u_1}$ необходимо определить по результатам $n + 1$ измерения. Для каждого уравнения рассмотрим невязку $r_k = u_1x_k + u_0 - f_k$ - разность левой и правой части. Невязка может принимать положительные и отрицательные значения. Чтобы не учитывать знаки, применим возведение в квадрат. Введем функцию, равную сумме квадратов невязок

( 2 )

$\Phi (u_1,u_0) = \sum\limits_{k = 0}^n {r_k^2} = \sum\limits_{k = 0}^n {(u_1 x_k + u_0 - f_k)^2}$

Примем за обобщённое решение переопределённой СЛАУ такие ${u_0, u_1}$ , для которых $\Phi(u_0, u_1)$ принимает наименьшие значение. Для определения обобщенного решения из условия минимума суммы квадратов невязки получаем систему двух уравнений, уже имеющую классическое решение:

$\frac{\partial \Phi }{\partial u_0} = 0,\ \frac{\partial \Phi }{\partial u_1} = 0.$

Рассмотрим теперь общий случай. Определим невязку $r_k$ в виде

$r_k = \sum\limits_{j = 0}^p {u_j\varphi_j (x_k)} - f(x_k),\ k = 1, \ldots, n,$

где $\varphi_j (x)$ — некоторые функции, образующие базис, например, тригонометрические: $\varphi_j (x) = \sin (jx)$ . Выражение $\sum\limits_{j = 0}^p {u_j \varphi_j (x)}$ называется обобщенным полиномом. В приведенном выше примере в качестве базисных функций были выбраны степенные функции $\varphi_j (x) = x^j$ . Обобщенный полином превратился в алгебраический.

В случае выбора произвольной системы базисных функций переопределенная СЛАУ и функционал $\Phi(u_0, \dots, u_p)$ будут иметь вид

$\begin{gather*} u_0 \varphi_0 (x_0) + \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*}$

Отыщем обобщенное решение методом наименьших квадратов: приравняем все частные производные по компонентам обобщенного решения к нулю $\frac{\partial \Phi }{\partial u_k} = 0$ (условия минимума) и изменяя порядок суммирования, получаем СЛАУ:

$\sum\limits_{j = 0}^p {\left({\sum\limits_{i = 0}^n{\varphi_j (x_i)\varphi_k (x_i)}}\right)u_j = \sum\limits_{i = 0}^n {f_i\varphi_k (x_i)}},\ k = 0, \ldots, p,$

или, в виде системы уравнений:

$\begin{gather*} (\varphi_0, \varphi_0) 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*}$

Система метода наименьших квадратов имеет вид $\mathbf{Du} = \mathbf{f}$ с матрицей $\mathbf{D}$ , элементами которой являются скалярные произведения $(\varphi_i, \varphi_j) = \sum\limits_{i = 0}^n \varphi_j (x) \varphi_k (x_i)$ . Это — матрица Грамма. Ее свойства известны из курса линейной алгебры, эта матрица симметричная и положительно определенная. Таким образом, решение исследуемой СЛАУ существует и единственно. В правой части системы стоят проекции свободного члена исходной задачи на подпространство базисных функций $(\varphi,f) = \sum\limits_{i = 0}^n {\varphi_j(x_i)f_i}$ .

Здесь учтено, что $\frac{\partial \Phi }{\partial u_k} = 2 \sum\limits_{i = 0}^n {\varphi_k(x_i)\left({\sum\limits_{j = 0}^p {u_j\varphi_j (x_i) - f_i}} \right)}$ .