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

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

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

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

2. Метод покоординатного спуска

3. Метод градиентного спуска

4. Метод сопряженных градиентов

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

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

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

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

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

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

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

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

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

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

Получаем, что точку минимума, мы можем найти из уравнения 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:

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

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

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

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

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

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

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

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

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

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