Вычислительная математика

     .

    Решением  данной системы будут значения: х₁=1; х₂=1 

    Изменим правые части на некоторую величину(3,2; 3,1): .

    Тогда х₁=1 х₂= 1,1.

     .

    Матрица симметричная, из диагональных элементов  вычитаем :

     = 0

    

    

    

    Как и следовало ожидать, система  очень чувствительна к ошибке в задании правых частей системы  уравнений.

    Обусловленность матрицы  , т.е. матрица системы достаточно хорошо обусловлена, но, тем не менее, необходимо применять методы повышения устойчивости решения. 

2.2. Определение псевдообратной матрицы

для произвольной матрицы на основе метода ортогонализации Грамма-Шмидта (ГШО). 

2.2.1Столбцы матрицы , которые обозначим , преобразуются методом ГШО в ортогональные векторы (не обязательно, чтобы они получились ортонормированными). Из множества этих векторов образуется матрица .

     Ортогонализация столбцов матрицы методом ГШО производится по уравнениям ;

      , (10)

где .

     Здесь - норма вектора, определяемая выражением .

     Сравнивая нормы векторов , принимают решение об обнулении вектора с малой нормой.

2.2.2Столбцы матрицы переставляются с помощью матрицы перестановок таким образом, что

, (11)

где

     Матрица перестановок может быть подобрана следующим образом. Если требуется поменять местами i – столбец и j – столбец, то в единичной - матрице нужно сделать следующие замены: ; . В общем случае матрица может включать произведение нескольких перестановочных матриц.

2.2.3.Столбцы исходной матрицы переставляются с помощью матрицы перестановок , применяемой в п.2. При этом получают новую матрицу со столбцами, которые обозначим, например, так:

      ;

      .

2.2.4.Вычисляются вспомогательные коэффициенты

     

2.2.5.Вычисляется матрица размером с элементами

      .

2.2.6.Вычисляется матрица размером с элементами

     

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

      .

     Здесь размер матриц ;

      ; 

      ; 

      .

2.2.8.Вычисляется матрица .

2.2.9.Используя матрицу, полученную в (11), вычисляем матрицу

      .

2.2.10.С помощью вспомогательных матриц , , , , , вычисленных в пп. 2, 5, 6, 8, 9, определяется псевдообратная матрица

      .

     Оценка  коэффициентов линейной регрессии  определяется выражением . 

    2.3.Построение псевдообратной матрицы на основе метода ортогонализации Грамма-Шмидта. 

Определяем ортогональные векторы

     ;   ;

     ;   . 

    Сравнивая нормы, принимаем решение, что второй вектор исходной матрицы  является линейно зависящим от первого вектора и им можно пренебречь, т.е. .

Число независимых столбцов k=1. 

    Матрица перестановок .

;   .

Определяем  значения необходимых вспомогательных  коэффициентов:

В=

Q=

Псевдообратная  матрица:

Решение при «точных» данных

     .

     Решение при измененной правой части  

     .

 

     

3. Решение  нелинейных  уравнений на основе  метода минимизации  функций многих  переменных. 

3.1. Формирование нелинейной  функции многих  переменных

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

       Ф = Ф(X₁,X₂,…,X_n).                                                               (1)

       Определение оптимального управления сводится к  поиску такого набора численных значений переменных, при котором функция Ф достигает экстремального значения. Для определенности будут рассматриваться только минимумы функции.

      Функцию можно задавать в виде точного  описания последовательности операций над численными значениями переменных X₁,X₂,…,X_n. Функция должна обладать свойством однозначности, т.е. при любом наборе численных значений  X₁,X₂,…,X_n принимать только одно значение.

      Будем считать набор численных значений  X₁,X₂,…,X_n координатами некоторой точки n-мерного пространства, которую можно представить вектором . Для такой точки можно подсчитать значения функции . Выделим из совокупности точек n-мерного пространства те точки, которым соответствуют равные значения функции , где Ф₀ – некоторое численное значение. Геометрическое место точек с равными значениями функции называют поверхностью равного уровня. Изменив уровень Ф₀ функции, получим другую поверхность равного уровня, причем различные поверхности равных уровней вложены одна в другую, но нигде не соприкасаются. Отсутствие общих точек у этих поверхностей непосредственно следует из свойства однозначности функции.

     Градиентом  функции будем называть вектор

      ,    (2)

где частные производные функции вычислены в точке . В n-мерном пространстве градиент направлен перпендикулярно (нормально)  к поверхности равного уровня в точке и указывает направление наискорейшего возрастания функции. Противоположный по направлению вектор , называемый антиградиентом, дает направление наискорейшего убывания функции. В различных методах поиска минимума функции можно выделить два основных этапа: определение направления и минимизацию функции в этом направлении. Методы минимизации многомерных функций различаются способами реализации этих этапов. В одних методах векторы направлений наперед заданы (координатный спуск в методе Гаусса-Зейделя), а в других выбор направления зависит от поведения функции как, например, в рассматриваемом градиентном методе Давидона-Флетчера-Пауэлла (ДФП). Второй этап – минимизация функции в выбранном направлении – представляет собой одномерный поиск и наиболее трудоемкую часть процесса. Рассмотрим теперь подробнее градиентный метод ДФП. 

     Исходные  данные: начальная точка поиска ; градиент функции ; градиент функции в начальной точке нормируется по уравнению ,

       где  ; ; начальная матрица n×n, равная единичной матрице, H(1,1) = E[1,1]; ε - коэффициент, задающий точность одномерного поиска; Δ – точность поиска минимума функции.

1. Вычисляем вектор направления .  (3)
2. Формируем вектор                                 (4)

и, изменяя  параметр α, проводим в направлении одномерный поиск минимума функции. По его результатам определяем положение оптимальной конечной точки на этом направлении: ; .

     Начальное значение шага одномерного поиска α₀ принимается равным 1, если выполняется условие , иначе величина уменьшается. регулировка масштаба одномерного поиска заложена в формуле (3), так как величина модуля зависит от модуля градиента и по мере приближения к минимуму функции неограниченно убывает. Уменьшение шага поиска по мере приближения к минимуму многомерной функции является необходимым, иначе трудно будет достаточно точно определить координаты этого минимума.

      3. Вычисляем градиент  и приращение градиента

       .                                      (5)

       4. Находим  новую матрицу Н по рекуррентной формуле

       .                  (6)

      5. Переходим на этап 1 с новыми  начальными условиями. 

       Отметим некоторые  вычислительные особенности метода ДФП. Метод подвержен накоплению ошибок, вследствие чего рекомендуется время от времени «забывать» накопленную информацию и начинать вычислительный процесс заново. Для этого необходимо предусмотреть «обновление» расчетов. Оно заключается в замене с некоторой периодичностью (обычно через n или 2n итераций) текущей матрицы Н единичной матрицей Е.

      При обновлении на каждой итерации метод ДФП  превращается в метод  наискорейшего спуска.

     При расчете на ЭВМ первая производная  функции по некоторому параметру X_i заменяется первой разделенной разностью

      ,                                    (7)

где X₁, X_i, X_n  - координаты точки , в которой вычисляется производная. 

     Для метода ДФП рассматриваются 2 варианта реализации, которые различаются  только методами одномерного поиска. В первом варианте применяется метод золотого сечения, во втором – квадратичная аппроксимация. Рассмотрим кратко эти методы. 

3.2. Сокращение интервала неопределенности методом золотого сечения 

Пусть задана функция  F=

       Для нахождения минимума функции необходимо прежде всего определить интервал неопределенности, т.е. отрезок на прямой, внутрь которого попадает точка X_m с минимальным значением функции F(X_m). Для ускорения поиска на этапе выделения интервала неопределенности необходимо ввести переменный шаг в (4):

       ; α_-1 = 0; α₀ = 1,                                     (8)

если  при этом происходит убывание функции.

       На  рис. 1 изображена последовательность точек α₀, α₁, α₂ , полученная согласно алгоритму (8).