Участник:Василий Ломакин/Решение переопределенной СЛАУ
Материал из MachineLearning.
м |
|||
(6 промежуточных версий не показаны.) | |||
Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
+ | Рассмотрим прямоугольную матрицу размером <tex>m \times n</tex>: | ||
+ | <p align="center"><tex> | ||
+ | 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). | ||
+ | </tex></p> | ||
+ | Пусть в матрице число строк превышает число столбцов (<tex>m > n</tex>), причём все строки линейно независимы. | ||
+ | Систему уравнений вида | ||
+ | {{ eqno | 1 }} | ||
+ | <p align="center"><tex>Au=f</tex>,</p> | ||
+ | где <tex>A</tex> - описанная выше, <tex>{u}={\{u_1, \ldots , u_n \}}^T</tex> — вектор-столбец решения, <tex>{f}={\{f_1, \ldots , f_n \}}^T</tex> — вектор-столбец правой части, назовём '''переопределённой'''. Как можно видеть, в такой системе число уравнений превышает число неизвестных, и для неё не существует "классического" решения. | ||
== Изложение метода == | == Изложение метода == | ||
+ | Приведем простой пример получения переопределённой системы линейных уравнений. Такого рода задачи часто встречаются, например, при обработке результатов экспериментов. Пусть <tex>f</tex> — линейная (или близкая к линейной) функция аргумента <tex>x:\ f(x) = u_1x + u_0</tex>. В точках <tex>x_k</tex> известны значения функции <tex>f(x_k)</tex>. Тогда <tex>u_0,\ u_1</tex> — коэффициенты, которые необходимо подобрать так, чтобы выполнялись условия <tex>u_1x_k + u_0 = f_k,\ k = 0,1,2,3,4,\ f_k = f(x_k)</tex>. Получим систему пяти уравнений относительно двух неизвестных. Это — переопределённая система. Она не имеет классического решения, так как в общем случае не существует прямой, проходящей через все 5 точек (это возможно только тогда, когда какие - либо три уравнения полученной системы линейными преобразованиями сводятся к двум другим — система линейно зависима). Необходимо провести аппроксимирующую кривую, которая не проходит через экспериментальные точки, но в то же время отражает экспериментальную зависимость, сглаживает возможные выбросы за счёт погрешности эксперимента. | ||
+ | Рассмотрим более общий случай. Пусть коэффициенты <tex>{u_0,\ u_1}</tex> необходимо определить по результатам <tex>n + 1</tex> измерения. Для каждого уравнения рассмотрим невязку <tex>r_k = u_1x_k + u_0 - f_k</tex> - разность левой и правой части. Невязка может принимать положительные и отрицательные значения. Чтобы не учитывать знаки, применим возведение в квадрат. Введем функцию, равную сумме квадратов невязок: | ||
+ | {{ eqno | 2 }} | ||
+ | <p align="center"><tex>\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}</tex></p> | ||
+ | Примем за обобщённое решение переопределённой СЛАУ такие <tex>{u_0,\ u_1}</tex>, для которых <tex>\Phi(u_0,\ u_1)</tex> принимает наименьшие значение. Для определения обобщённого решения из условия минимума суммы квадратов невязки получаем систему двух уравнений, уже имеющую классическое решение: | ||
+ | <p align="center"><tex>\frac{\partial \Phi }{\partial u_0} = 0,\ \frac{\partial \Phi }{\partial u_1} = 0.</tex></p> | ||
- | == | + | Рассмотрим теперь '''общий случай'''. Определим невязку <tex>r_k</tex> в виде |
+ | <p align="center"><tex>r_k = \sum\limits_{j = 0}^p {u_j\varphi_j (x_k)} - f(x_k),\ k = 1, \ldots, n,</tex></p> | ||
+ | где <tex>\varphi_j (x)</tex> — некоторые функции, образующие базис, например, тригонометрические: <tex>\varphi_j (x) = \sin (jx)</tex> . Выражение <tex>\sum\limits_{j = 0}^p {u_j \varphi_j (x)}</tex> называется обобщённым полиномом. В приведенном выше примере в качестве базисных функций были выбраны степенные функции <tex>\varphi_j (x) = x^j</tex> . Обобщённый полином превратился в алгебраический. | ||
- | == | + | В случае выбора произвольной системы базисных функций переопределенная СЛАУ и функционал <tex>\Phi(u_0, \dots, u_p)</tex> будут иметь вид |
+ | <p align="center"><tex>\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*}</tex></p> | ||
+ | |||
+ | Отыщем обобщенное решение методом наименьших квадратов: приравняем все частные производные по компонентам обобщенного решения к нулю (условия минимума): | ||
+ | <p align="center"><tex>\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)}=0</tex></p> | ||
+ | и изменяя порядок суммирования, получаем СЛАУ: | ||
+ | <p align="center"><tex>\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,</tex></p> | ||
+ | или, в виде системы уравнений: | ||
+ | <p align="center"><tex>\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*}</tex></p> | ||
+ | |||
+ | Система метода наименьших квадратов имеет вид <tex> \mathbf{Du} = \mathbf{f}</tex> с матрицей <tex>\mathbf{D}</tex>, элементами которой являются скалярные произведения <tex>(\varphi_i, \varphi_j) = \sum\limits_{i = 0}^n \varphi_j (x) \varphi_k (x_i)</tex>: | ||
+ | |||
+ | <p align="center"><tex> | ||
+ | \begin{vmatrix} | ||
+ | (\varphi_0,\ \varphi_0) & (\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}. | ||
+ | </tex></p> | ||
+ | |||
+ | Это — матрица Грама. В правой части системы стоят проекции свободного члена исходной задачи на подпространство базисных функций <tex>(\varphi,f) = \sum\limits_{i = 0}^n {\varphi_j(x_i)f_i}</tex>. Матрица симметричная и положительно определенная, таким образом, решение исследуемой СЛАУ существует и единственно. Находится, например, с помощью итерационного метода Гаусса. | ||
+ | |||
+ | == Советы программисту == | ||
+ | |||
+ | Отметим основные свойства матрицы Грама, полезные при программировании: | ||
+ | # Матрица симметрична, что позволяет сократить объём вычислений при заполнении матрицы. | ||
+ | # Матрица является положительно определённой, следовательно, при решении системы нормальных уравнений методом исключения Гаусса можно отказаться от процедуры выбора главного элемента. | ||
+ | # Определитель матрицы будет отличен от нуля, если в качестве базиса выбраны линейно независимые функции, при этом система имеет единственное решение. | ||
+ | # При обработке экспериментальных данных, определённых с погрешностью <tex>\varepsilon</tex> в каждой точке, обычно сначала берут небольшое (одну-две) число базисных функций. После вычисления приближённого решения, вычисляют сумму квадратов невязок по формуле, аналогичной {{eqref|2}}. Если получается, что <tex>sqrt{\Phi} > \varepsilon</tex>, то необходимо расширить базис добавлением новых функций. Расширение базиса необходимо производить до тех пор, пока не выполнится условие <tex>\sqrt{\Phi} \approx \varepsilon</tex>. | ||
+ | # Выбор конкретных базисных функций зависит от свойств функции <tex>f</tex>, таких как периодичность, экспоненциальный или логарифмический характер, свойства симметрии, наличие асимптотики и т.д. | ||
== Список литературы == | == Список литературы == | ||
- | * '' | + | * ''А.Е.Мудров'' Численные методы для ПЭВМ. Томск: Раско, 1991. |
* ''А.А.Самарский, А.В.Гулин.'' Численные методы М.: Наука, 1989. | * ''А.А.Самарский, А.В.Гулин.'' Численные методы М.: Наука, 1989. | ||
== См. также == | == См. также == | ||
* [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]] | * [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]] | ||
+ | * [[Метод наименьших квадратов|Метод наименьших квадратов]] |
Текущая версия
Содержание |
Постановка задачи
Рассмотрим прямоугольную матрицу размером :
Пусть в матрице число строк превышает число столбцов (), причём все строки линейно независимы. Систему уравнений вида
,
где - описанная выше, — вектор-столбец решения, — вектор-столбец правой части, назовём переопределённой. Как можно видеть, в такой системе число уравнений превышает число неизвестных, и для неё не существует "классического" решения.
Изложение метода
Приведем простой пример получения переопределённой системы линейных уравнений. Такого рода задачи часто встречаются, например, при обработке результатов экспериментов. Пусть — линейная (или близкая к линейной) функция аргумента . В точках известны значения функции . Тогда — коэффициенты, которые необходимо подобрать так, чтобы выполнялись условия . Получим систему пяти уравнений относительно двух неизвестных. Это — переопределённая система. Она не имеет классического решения, так как в общем случае не существует прямой, проходящей через все 5 точек (это возможно только тогда, когда какие - либо три уравнения полученной системы линейными преобразованиями сводятся к двум другим — система линейно зависима). Необходимо провести аппроксимирующую кривую, которая не проходит через экспериментальные точки, но в то же время отражает экспериментальную зависимость, сглаживает возможные выбросы за счёт погрешности эксперимента.
Рассмотрим более общий случай. Пусть коэффициенты необходимо определить по результатам измерения. Для каждого уравнения рассмотрим невязку - разность левой и правой части. Невязка может принимать положительные и отрицательные значения. Чтобы не учитывать знаки, применим возведение в квадрат. Введем функцию, равную сумме квадратов невязок:
Примем за обобщённое решение переопределённой СЛАУ такие , для которых принимает наименьшие значение. Для определения обобщённого решения из условия минимума суммы квадратов невязки получаем систему двух уравнений, уже имеющую классическое решение:
Рассмотрим теперь общий случай. Определим невязку в виде
где — некоторые функции, образующие базис, например, тригонометрические: . Выражение называется обобщённым полиномом. В приведенном выше примере в качестве базисных функций были выбраны степенные функции . Обобщённый полином превратился в алгебраический.
В случае выбора произвольной системы базисных функций переопределенная СЛАУ и функционал будут иметь вид
Отыщем обобщенное решение методом наименьших квадратов: приравняем все частные производные по компонентам обобщенного решения к нулю (условия минимума):
и изменяя порядок суммирования, получаем СЛАУ:
или, в виде системы уравнений:
Система метода наименьших квадратов имеет вид с матрицей , элементами которой являются скалярные произведения :
Это — матрица Грама. В правой части системы стоят проекции свободного члена исходной задачи на подпространство базисных функций . Матрица симметричная и положительно определенная, таким образом, решение исследуемой СЛАУ существует и единственно. Находится, например, с помощью итерационного метода Гаусса.
Советы программисту
Отметим основные свойства матрицы Грама, полезные при программировании:
- Матрица симметрична, что позволяет сократить объём вычислений при заполнении матрицы.
- Матрица является положительно определённой, следовательно, при решении системы нормальных уравнений методом исключения Гаусса можно отказаться от процедуры выбора главного элемента.
- Определитель матрицы будет отличен от нуля, если в качестве базиса выбраны линейно независимые функции, при этом система имеет единственное решение.
- При обработке экспериментальных данных, определённых с погрешностью в каждой точке, обычно сначала берут небольшое (одну-две) число базисных функций. После вычисления приближённого решения, вычисляют сумму квадратов невязок по формуле, аналогичной (2). Если получается, что , то необходимо расширить базис добавлением новых функций. Расширение базиса необходимо производить до тех пор, пока не выполнится условие .
- Выбор конкретных базисных функций зависит от свойств функции , таких как периодичность, экспоненциальный или логарифмический характер, свойства симметрии, наличие асимптотики и т.д.
Список литературы
- А.Е.Мудров Численные методы для ПЭВМ. Томск: Раско, 1991.
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.