Участник:Василий Ломакин/Решение переопределенной СЛАУ
Материал из MachineLearning.
| Строка 29: | Строка 29: | ||
<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> | <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>. Это — матрица | + | Система метода наименьших квадратов имеет вид <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>. Это — матрица Граммммммммма. В правой части системы стоят проекции свободного члена исходной задачи на подпространство базисных функций <tex>(\varphi,f) = \sum\limits_{i = 0}^n {\varphi_j(x_i)f_i}</tex>. Как известно, решение такой СЛАУ существует и единственно, находится, например, с помощью итерационного метода Гаусса. |
Здесь учтено, что | Здесь учтено, что | ||
<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)}</tex>. | <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)}</tex>. | ||
| - | |||
| - | == | + | == Советы программисту == |
| + | |||
| + | Отметим основные свойства матрицы Грама, полезные при программировании: | ||
| + | # Матрица симметрична, что позволяет сократить объём вычислений при заполнении матрицы. | ||
| + | # Матрица является положительно определённой, следовательно, при решении системы нормальных уравнений методом исключения Гаусса можно отказаться от процедуры выбора главного элемента. | ||
| + | # Определитель матрицы будет отличен от нуля, если в качестве базиса выбраны линейно независимые функции, при этом система имеет единственное решение. | ||
| + | # При обработке экспериментальных данных, определённых с погрешностью ЭПС в каждой точке, обычно сначала берут небольшое (одну-две) число базисных функций. После вычисления приближённого решения, вычисляют сумму квадратов невязок по формуле, аналогичной {{eqref|2}}. Если получается, что КОРЕНЬ ИЗ ФИ больше ЭПС, то необходимо расширить базис добавлением новых функций. Расширение базиса необходимо производить до тех пор, пока не выполнится условие КОР ИЗ ФИ ПРИМЕРНО РАВНО ЭПС. | ||
| + | # Выбор конкретных базисных функций зависит от свойств функции F, таких как периодичность, экспоненциальный или логарифмический характер, свойства симметрии, наличие асимптотики и т.д. | ||
| + | |||
| + | |||
| + | |||
== Список литературы == | == Список литературы == | ||
Версия 15:08, 12 ноября 2008
Содержание |
Постановка задачи
Рассмотрим прямоугольную матрицу размером :
Пусть в матрице число строк превышает число столбцов (), причём все строки линейно независимы.
Систему уравнений вида
,
где А - описанная выше, — вектор-столбец решения,
— вектор-столбец правой части, назовём переопределённой. Как можно видеть, в такой системе число уравнений превышает число неизвестных, и для неё не существует "классического" решения, например методом Гаусса.
Изложение метода
Приведем простой пример получения переопределённой системы линейных уравнений. Такого рода задачи часто встречаются, например, при обработке результатов экспериментов. Пусть — линейная (или близкая к линейной) функция аргумента
. В точках
известны значения функции
. Тогда
— коэффициенты, которые необходимо подобрать так, чтобы выполнялись условия
. Получим систему пяти уравнений относительно двух неизвестных. Это — переопределённая система. Она не имеет классического решения, так как в общем случае не существует прямой, проходящей через все 5 точек (это возможно только тогда, когда какие - либо три уравнения полученной системы линейными преобразованиями сводятся к двум другим — система линейно зависима). Необходимо провести аппроксимирующую кривую, которая не проходит через экспериментальные точки, но в то же время отражает экспериментальную зависимость, сглаживает возможные выбросы за счёт погрешности эксперимента.
Рассмотрим более общий случай. Пусть коэффициенты необходимо определить по результатам
измерения. Для каждого уравнения рассмотрим невязку
- разность левой и правой части. Невязка может принимать положительные и отрицательные значения. Чтобы не учитывать знаки, применим возведение в квадрат. Введем функцию, равную сумме квадратов невязок
Примем за обобщённое решение переопределённой СЛАУ такие , для которых
принимает наименьшие значение. Для определения обобщенного решения из условия минимума суммы квадратов невязки получаем систему двух уравнений, уже имеющую классическое решение:
Рассмотрим теперь общий случай. Определим невязку в виде
где — некоторые функции, образующие базис, например, тригонометрические:
. Выражение
называется обобщенным полиномом. В приведенном выше примере в качестве базисных функций были выбраны степенные функции
. Обобщенный полином превратился в алгебраический.
В случае выбора произвольной системы базисных функций переопределенная СЛАУ и функционал будут иметь вид
Отыщем обобщенное решение методом наименьших квадратов: приравняем все частные производные по компонентам обобщенного решения к нулю (условия минимума) и изменяя порядок суммирования, получаем СЛАУ:
или, в виде системы уравнений:
Система метода наименьших квадратов имеет вид с матрицей
, элементами которой являются скалярные произведения
. Это — матрица Граммммммммма. В правой части системы стоят проекции свободного члена исходной задачи на подпространство базисных функций
. Как известно, решение такой СЛАУ существует и единственно, находится, например, с помощью итерационного метода Гаусса.
Здесь учтено, что
.
Советы программисту
Отметим основные свойства матрицы Грама, полезные при программировании:
- Матрица симметрична, что позволяет сократить объём вычислений при заполнении матрицы.
- Матрица является положительно определённой, следовательно, при решении системы нормальных уравнений методом исключения Гаусса можно отказаться от процедуры выбора главного элемента.
- Определитель матрицы будет отличен от нуля, если в качестве базиса выбраны линейно независимые функции, при этом система имеет единственное решение.
- При обработке экспериментальных данных, определённых с погрешностью ЭПС в каждой точке, обычно сначала берут небольшое (одну-две) число базисных функций. После вычисления приближённого решения, вычисляют сумму квадратов невязок по формуле, аналогичной (2). Если получается, что КОРЕНЬ ИЗ ФИ больше ЭПС, то необходимо расширить базис добавлением новых функций. Расширение базиса необходимо производить до тех пор, пока не выполнится условие КОР ИЗ ФИ ПРИМЕРНО РАВНО ЭПС.
- Выбор конкретных базисных функций зависит от свойств функции F, таких как периодичность, экспоненциальный или логарифмический характер, свойства симметрии, наличие асимптотики и т.д.
Список литературы
- Н.Н.Калиткин. Численные методы М.: Наука, 1978.
- А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
