Связь решения СЛАУ и минимума квадратичного функционла. Часть 1

Medium

4 min

3.5K

В цикле статей под общим названием «Связь решения СЛАУ и минимума квадратичного функционала» постараюсь осветить различные методы решения СЛАУ. Основная цель – написать понятный, но в то же время наполненный полезной информацией материал. К каждой последующей статье будет прилагаться соответсвующая реализиция на языке программирования C++.

Всего по плану написать 4 статьи:

Связь решения СЛАУ и минимума квадратичного функционала
Метод покоординатного спуска
Метод градиентного спуска
Метод сопряженных градиентов

Системы линейных алгебраических уравнений (СЛАУ) являются неотъемлемой частью современного мира, они могут возникнуть в ходе построения физических моделей, решения задач экономики и искусственного интеллекта. Хорошим примером междисциплинарного применяя СЛАУ служит расчет хода световых лучей согласно правилам волновой оптики в технологии RTX.

Выделяют два подхода при решении СЛАУ: точный и итерационный. Точный подход включает в себя методы Гаусса и Крамера, их относительно просто реализовать на каком-либо языке программирования. Но за простоту приходиться платить временем, при решении СЛАУ методом Гаусса время расчета может улететь в космос, если число уравнений больше десяти тысяч. Тут на помощь приходят итерационные методы, такие как покоординатный спуск, сопряженные градиенты и градиентный спуск. Практика показывает, что именно такие методы позволяют решать объемные СЛАУ за приемлемое время.

Озвученные итерационные методы связаны общей идеей - искать минимум функционала, а по дороги наткнуться на решение СЛАУ. Именно об этом подходе решения СЛАУ мы будем говорить.

Сперва вспомним, как вообще выглядит система линейных уравнений:

$\left\{ \begin{array}{cl} a_{11}x_{1}+a_{12}x_{2}+\cdots+a_{1n}x_{n}\\ a_{21}x_{1}+a_{22}x_{2}+\cdots+a_{2n}x_{n}\\ \cdots \\ a_{n1}x_{1}+a_{n2}x_{2}+\cdots+a_{nn}x_{n}\\ \end{array} \right.$

В общем случае, мы будем говорить, что это система n линейных алгебраических уравнений (СЛАУ порядка n). Всякое СЛАУ можно записать в матричной форме: AX=B, где

$A=\left(\begin{matrix}a_{11}&a_{12}&\ldots&a_{1n}\\a_{21}&a_{22}&\ldots&a_{2n}\\\ldots&\ldots&\ldots&\ldots\\a_{n1}&a_{n2}&\ldots&a_{nn}\\\end{matrix}\right), B=\begin{pmatrix} b_{1}\\ b_{2}\\ \vdots\\ b_{n} \end{pmatrix}, X=\begin{pmatrix} x_{1}\\ x_{2}\\ \vdots\\ x_{n} \end{pmatrix}$

Причем если мы положим n=1, то получим обыкновенное линейное уравнение, наподобие 5x=8. Замечание: в данном цикле мы рассматриваем только вещественный случай.

Теперь сделаем необычный шаг и наложим на основную матрицу системы A ограничение: Матрица А положительно определена. Что же такое положительно определенная матрица и зачем в контексте СЛАУ накладывать такое ограничение? На первый вопрос отвечу сразу:

Квадратная симметричная матрица A размерности n на n называется положительно определенной, когда для любого вектора X (кроме нулевого) координатного вещественного пространства R^n выполняется неравенство:

$(AX,X)\gt 0, \forall X \in R^n/\{\theta\}$

В дополнении советую прочитать про критерий Сильвестра.

Постепенно начнем отвечать на второй вопрос. Предлагаю рассмотреть функцию одной переменной:

Условие a > 0, дает нам основания утверждать, что наша функция, парабола, имеет строгий минимум. Найдем эту точку минимума:

$y'=2ax-2b=0 \to ax=b$

Получаем, что точку минимума, мы можем найти из уравнения ax=b. Таким образом мы можем сформировать утверждение: поиск минимума квадратичной функции y = ax^2-2b эквивалентен решению линейного уравнения ax=b.

А нельзя ли обобщить утверждение до многомерного случая? Конечно можно! Как говориться, в математике можно все, только мы не можем…

Для обобщения утверждения введем функционал (в данном случае это просто функция, у которой аргумент вектор столбец, (AX,X) - "классическое" склярное произведение в ортонормированном базисе) и построим теорему:

Теорема 1. Если в некоторой точке пространства R^n функционал F(X)=(AX,X)-2(B,X) имеет минимум, то координаты этой точки удовлетворяют системе AX=B, A - положительно определена.

Доказательстово довольно простое: Рассмотрим функционал F(X)=(AX,X)-2(B,X), который имеет минимум, отвечающий вектору X пространства R^n (A - положительно определена). δX - произвольный ненулевой вектор пространства R^n, будем называть его приращением аргумента. Рассмотрим значение функциинала в точке X+δX:

$F(X+ \delta X)= (AX+A\delta X, X+\delta X) - 2(X, X+\delta X) = \\ = (AX, X)+(AX, \delta X) +(A\delta X, X)+(A\delta X, \delta X) - 2(B, X)-2(B, \delta X) = \\ = (AX,X)-2(B,X)+2(AX, \delta X) - 2(B, \delta X) + (A\delta X, \delta X) = \\ = F(X) + 2(AX-B, \delta X) + (A\delta X, \delta X)$

Теперь построим приращение для функционала:

$\Delta F(X) =F(X+ \delta X) - F(X) =2(AX-B,\delta X) + (A\delta X, \delta X)$

В вариационном исчисление существует необходимое условие эестремума функционала, звучит оно следующим образом: Вариация функционала на экстримали равна нулю (можно проводить аналогию с производной функции, которая равна нулю в точке экстремума). Формула:

$\delta J (X_{0})=0$

По определению, вариацией функционала называется линейная часть его приращения (линейность относительно приращения аргумета, т. е. δX). В нашем случае равенство вариации нулю ставит СЛАУ:

$(AX-B,\delta X) = 0 \to AX-B=0\to AX=B$

Нелинейная часть приращения функционала определяет тип экстримали, в нашем случае это минимум, т. к. нелинейная часть положительна за счет положительной определенности матрицы A.

$(A\delta X, \delta X) > 0 \to X - min$

Почему мы рассматриваем только минимум? Потому что все методы, котрые мы будем рассматривать отталкиваются именно от минимума. Обобщенные методы тоже существуют, например метод бисопряженных градиентов.

Для полноты картины рассмотрим обратную теорему:

Теорема 2. Если X есть решение системы уравнений AX=B, то функционал F(X)=(AX,X)-2(B,X) имеет в точке X собственный абсолютный (единственный) минимум.

Доказательство: Если X решение системы AX=B, то вариация функионала равна нулю.

$AX=B \to AX-B=0\to (AX-B,\delta X) = 0$

Аналогично предыдущему доказательству нелинейная часть приращения функционала строго больше нуля, что говорит о том, что функционал имеет именно минимум. Решение СЛАУ однозначно, поэтому функионал имеет единственный минимум.

Примечание: основная матрица системы положительно определена, согласно критерию Сильвестра ее определитель строго больше нуля.

Окончательно можно сформировать утверждение: Задача поиска минимума квадратичного функционала F(X)=(AX,X)-2(B,X) эквивалентна решению системы линейных уравний AX=B.

Для закрепления материала рассмотрим такую систему:

$\left\{ \begin{array}{cl} x+y=3\\ x+2y=1\\ \end{array} \right. \text{, Решение: } X=\begin{pmatrix} 5 \\ -2 \end{pmatrix} \\ F(\begin{pmatrix} x \\ y \end{pmatrix}) = ( \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix}, \begin{pmatrix} x \\ y \end{pmatrix} ) - 2( \begin{pmatrix} 3 \\ 1 \end{pmatrix}, \begin{pmatrix} x \\ y \\ \end{pmatrix} ) = x^2+2xy+2y^2-6x-2y$

Построив грфик, однозначно можно убедиться, что решение СЛАУ AX=B есть минимум функионал F(X).

Отображение функционала и точка минимума

В следущий раз мы рассмотрим самый простой метод нахождения минимум квадратичного функционала F(X) - метод покоординатного спуска.

Tags:

Hubs: