Тема № 4

Аналитическое моделирование (6 часов)

 

Введение

В этой теме мы рассмотрим моделирование эпидемий, методы анализа аналитической модели, итерационные методы,  точные методы решения систем линейных алгебраических уравнений.

 

План:

1.     Моделирование эпидемий - пример построения аналитической математической модели.

2.     Методы анализа аналитической модели.

3.     Общая процедура решения уравнений. Дихотомия.

4.     Итерационные методы хорд и касательных.

5.     Порядок сходимости метода. Ускорение сходимости.

6.     Точные методы решения систем линейных алгебраических уравнений.

7.     Итерационные процедуры и их сходимость к решению.

8.     Понятие о плохо обусловленных системах.

9.     Регуляция систем с большим количеством обусловленности.

1. Моделирование эпидемий - пример построения аналитической математической модели.

Линейная модель «Эпидемия» как пример самоподдерживающегося процесса. Это модель 2 типа.

1) интенсивность падает с ростом количественных показателей процесса, то течение такого процесса тривиально, он затухает с течением времени;

2) самоподдерживающийся процесс.

 «Эпидемия»: чем больше больных, тем больше заражающихся.

Основа построения: метод аналогии.

Шаг 1: закон теплопроводности –  Tt=kTXX.

T(x,t) – Т в точке ч в момент времени,

k – коэффициент теплопроводности.

Влияние среды не уточняется.

Шаг 2: Влияние среды (qT) прямо пропорционально температуре.

Tt=kTXX+qT

Интенсивность горения прямо пропорционально температуре. Данное уравнение описывает линейную модель процесса горения в некоторой среде с линейным источником горения.

Шаг 3: Переход от линейного источника к кубической зависимости:

qT-aT3 – среда с кубическим источником энергии.

Tt=kTXX+qT-aT3,

где a,q – параметры источника среды.

Шаг 4: Улучшение вида источника, возьмем конкретное Q. Q(T)=q0Tb. В конечном итоге необходимо получить линейную модель.

Tt=k(T)TXX + Q(T)k(T)=k0Td

где b > d+1, k0А0>0.

Это уравнение рассматривается во множестве научных трудов. Это усовершенствованная модель процесса горения в сложной среде.

В качестве вывода отмечу одно из больших преимуществ правильно построенной математической модели состоит в том, что она дает довольно точное описание структуры исследуемой эпидемии. С одной стороны, это позволяет в отсутствии практической проверки расширить наши теоретические знания по проблеме. Если основные уравнения можно решить аналитическим путем, то, подставляя в них различные значения рассматриваемых параметров, мы автоматически получаем решение всех возможных вариантов задачи. Кроме того, сама по себе аналитическая форма решений может углубить наши знания, позволяя выразить наблюдаемые биологические закономерности в виде математических теорем. Например, теорема эпидемий, которая может применяться в различных теориях. [2]

 

2. Методы анализа аналитической модели.

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

Методы исследования аналитического моделирования:

1) аналитический, используется тогда, когда стремятся получить в общем виде явные зависимости для искомых характеристик;

2) приближенный, используется тогда, когда решения представляются пределом некоторой последовательности аналитических функций, полученной по определенным правилам;

3) численный, используется когда не умея решать уравнения в общем виде стремятся получить численные результаты при конкретных начальных данных;

4) качественный, используется когда не имея решения в явном виде можно найти некоторые свойства решения.

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

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

Большое внимание при качественном исследовании математических моделей (или модельных задач для них) уделяется вопросам корректности. Прежде всего, рассматривается проблема существования решения. Соответствующие строгие результаты (теоремы существования) дают уверенность в корректности математической модели. Кроме того, конструктивные доказательства теорем существования могут быть положены в основу приближенных методов решения поставленной задачи.

При прикладном математическом моделировании важным является вопрос об устойчивости решения относительно малых возмущений входных данных. Неустойчивость (неограниченный рост решения при малых возмущениях) наиболее характерна для обратных задач и должна учитываться при построении приближенного решения.

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

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

Точное или приближенное решение находится с использованием аналитических и численных методов. В этой связи среди классических примеров аналитических методов отметим методы разделения переменных, интегральных преобразований для линейных задач математической физики.

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

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

Сложные нелинейные многопараметрические модели могут быть исследованы на компьютере численными методами. В отличие от аналитического решения, которое может давать явную параметрическую зависимость решения от тех или иных условий задачи, при численном решении требуется многократное решение задачи при изменении того или иного параметра. Но ведь численное решение может быть получено и для тех задач, для которых аналитического решения нет [2].

 

3. Общая процедура решения уравнений. Дихотомия.

В общем виде f(x)=0.

2 этапа решения не линейных уравнений:

1) определяются корни (находится отрезок, на котором содержится хотя бы один корень);

2) уточнения корня (находятся его значения с предварительно заданной точностью Є - эпсилон).

Решением называется любое значение Х, отличающееся от точного значения Х* по модулю не более чем на величину Є.  |Х-Х*|<= Є

На первом этапе пользуются свойством непрерывных функций: корни функции лежат между соседними экстремумами функции.

Во втором этапе лежит идея методов, которые можно рассматривать по 3-м направлениям:

·         поиск корня с заданной погрешностью сводится к перебору всех возможных значений аргумента с проверкой на наличие решений;

·         поиск корня не линейной функции заменяется поиском корня какой-либо простой функции (линейной/параболической), близкой к исходной нелинейной;

·         нелинейные уравнения вида F(X)=0 сводятся к одной из форм вида g(X)=h(X), где стремятся получить равенства правой и левой части (с помощью итерации).

Условием окончания процесса решения уравнения может быть:

1) |F(X*)|<δ;

2) |X*-XK|<Є.

При решении математических задач важными являются 2 цели:

·     обеспечение близости к 0 F(X);

·     обеспечение точности нахождения решения Х*.

Любое уравнение можно привести к виду:

F(x)=aNxN+aN-1xN-1+…+a0.

Методы отделения корней:

·     графически, на графике точка пересечения является решением;

·     аналитически, F(x*)=0, ищем экстремумы функции (точки).

Пример: F(x)=x4-x3-2x2-3x-3

a) F(x)=0

  F´(x)=4x3-3x2-4x-3 = 4x(x2-1)-3(x2-1) = (4x-3)´(x2-1)

X

-¥

-2

-1

3¤4

1

2

+¥

Знак Х

+

+

-

-

-

+

+

б) (-2,1), (1,2) на этих промежутках ищем корни.

 

Концепция методов решения систем не линейных уравнений

Решение систем не линейных уравнений F(x)=0,

где Х – векторная величина,

F(X) – векторная функция.

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

В основном используют 2 метода:

·     метод Ньютона - Рафсона;

·     метод итераций. [3]

 4. Итерационные методы хорд и касательных.

1) метод хорд.

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

Для вогнутой кривой, если F(b)F’’(b)>0

Для выпуклой кривой, если F(а)F’’(а)>0

2) метод Ньютона (или касательных).

В качестве начальной точки берется: левая точка, если F(a)F’’(a)>0; правая точка, если F(b)F’’(b)>0.

3) метод простой итерации.

(1)

 
 


 

Берем какую-то точку Х0 и подставляем в (1)   . В конечном итоге получится, что . Затем вместо Х0 ставим Х1, и получаем Х2, т.е.  и т.д. до тех пор пока не приблизимся к точке.

если другой график g(x)=x

 

5. Порядок сходимости метода. Ускорение сходимости.

Метод Ньютона

Отличие этого итерационного метода от метода хорд состоит в том, что вместо хорды на каждом шаге проводится касательная к кривой y = f(x) при x = хi и ищется точка пересечения касательной с осью абсцисс (Рис. 1). При этом не обязательно задавать отрезок [а, b], содержащий корень уравнения (1), достаточно найти лишь некоторое начальное приближение корня x = х0.

Применяя метод Ньютона, следует руководствоваться следующим правилом: в качестве исходной точки х0 выбирается тот конец интервала [а, b], которому отвечает ордината того же знака, что и знак f'' (х).

Рис. 1.

 Уравнение касательной, проведенной к кривой y = f(x) через точку В0 с координатами х0 и f(х0), имеет вид:

Отсюда найдем следующее приближение корня х1 как абсциссу точки пересечения касательной с осью Ох (y = 0):

 

Аналогично могут быть найдены и следующие приближения как точки пресечения с осью абсцисс касательных, проведенных в точках В1, В2 и так далее. Формула для i +1 приближения имеет вид:

(2)

Для окончания итерационного процесса может быть использовано или условие | f(xi)| < e , или условие близости 2х последовательных приближений | xi - xi - 1 | < e .

Итерационный процесс сходится если

f(х0) * f'' (х0) > 0.

 

Метод простой итерации

 Для использования метода итерации исходное нелинейное уравнение f(х) = 0 заменяется равносильным уравнением

x = j(x).

(3)

Пусть известно начальное приближение корня х = х0. Подставляя это значение в правую часть уравнения (3), получим новое приближение:

х1 = j(х0).

 

Далее, подставляя каждый раз новое значение корня в (3), получаем последовательность значений:

(4)

Геометрически метод итерации может быть пояснен следующим образом. Построим на плоскости хОу графики функций у = х и у = j (х). Каждый действительный корень уравнения (3) является абсциссой точки пересечения М кривой у = j (х) с прямой у = х (Рис. 2, а).

Рис. 2.

Отправляясь от некоторой точки А0 [x0, j (x0)], строим ломаную А0В1А1В2А2... (“лестница”), звенья которой попеременно параллельны оси Ох и оси Оу, вершины А0, А1, А2...лежат на кривой у=j (х), а вершины В1, В2, В3, …, - на прямой у = х. Общие абсциссы точек А1 и В1, А2 и В2, ..., очевидно, представляют собой соответственно последовательные приближения х1, х2, ... корня .

Возможен также другой вид ломаной А0В1А1В2А2 ... - “спираль” (Рис. 2, б). Решение в виде “лестницы” получается, если производная j' (х) положительна, а решение в виде “спирали”, если j' (х) отрицательна.

На Рисунке 6, а, б кривая у = j (х) в окрестности корня - пологая, то есть <1, и процесс итерации сходится. Однако, если рассмотреть случай, где >1, то процесс итерации может быть расходящимся (Рис. 3).

Рис. 3.

 Поэтому для практического применения метода итерации нужно выяснить достаточные условия сходимости итерационного процесса.

Теорема: Пусть функция j (х) определена и дифференцируема на отрезке [a, b], причем все ее значения j (х) inclusion.gif (64 bytes)[a, b].

Тогда, если существует правильная дробь q такая, что q < 1 при a < x < b, то:

1) процесс итерации  сходится независимо от начального значения х0 I [a, b];

2) предельное значение является единственным корнем уравнения х = j (х) на отрезке [a, b].

Пример 1. Уравнение

f(x) = x3 - x - 1 = 0

(5)

имеет корень x inclusion.gif (64 bytes)[1, 2], так как f(1) = - 1 < 0 и f(2) = 5 > 0.

Уравнение (5) можно записать в виде

х = х3 - 1.

(6)

Здесь

j (х) = х3 - 1 и j' (х) = 3х2;

поэтому

j' (х) more.gif (65 bytes)3 при 1 less.gif (65 bytes)х less.gif (65 bytes)2

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

Если записать уравнение (5) в виде

(7)

 

то будем иметь:

 

 

Отсюда  при 1 less.gif (65 bytes)х less.gif (65 bytes)2 и значит, процесс итерации для уравнения (12) быстро сойдется.

Найдем корень x уравнения (10) с точностью до 10-2. Вычисляем последовательные приближения хn с одним запасным знаком по формуле

  (i=0,1,2, …).

Найденные значения помещены в таблицу 1:

Таблица 1

Значения последовательных приближений xi.

i

0

1

2

3

4

xi

1

1,260

1,312

1,322

1,3243

С точностью до 10-2 можно положить x = 1,324.

 

 

6. Точные методы решения систем линейных алгебраических уравнений.

 

Методы решения систем линейных уравнений:

·         точные методы;

·         итерационные методы.

 

Точные методы представляют собой конечный алгоритм для получения точного решения.

К точным методам относятся:

·     метод Крамера;

·     метод Гаусса;

·     метод главных элементов.

 

 

Метод Крамера

 

    Пусть дана система линейных уравнений

 

           (1)

 

     Коэффициенты a11,12,..., a1n, ... , an1 , b2 , ... , bn   считаются заданными.

Вектор - строка íx1  , x2  , ... , xn  ý - называется решением системы (1), если при подстановке этих чисел вместо переменных все уравнения системы (1) обращаются в верное равенство.

       Определитель n-го порядка DAê=ça ij  ç, составленный из коэффициентов при неизвестных, называется определителем системы (1). В зависимости от определителя системы (1) различают следующие случаи.

a)      если D¹0, то система (1) имеет единственное решение, которое может быть найдено по формулам Крамера: 

x1=,

 

где определитель n-го порядка Di (i=1,2,...,n) получается из определителя системы путем замены i-го столбца свободными членами b1 , b2 ,..., bn;        

б) если D=0 , то система (1) либо имеет бесконечное множество решений, либо несовместна, т.е. решений нет.

 

Рассмотрим систему 3-х линейных уравнений с тремя неизвестными. [3]

 

 

         (2)

 

1.      В данной системе составим определитель 

  и вычислим.

 

 2. Составим и вычислим следующие определители:

 

      .

 

   3. Воспользуемся формулами Крамера:

 

     

 

ПРИМЕР:

_______________

 

1. .

 

     

 

   

                          

 

 

                              .

 

 

     Проверка:

 

 

                                   Ответ:  (3; -1).

 

 

 

Метод Гаусса

 

    Пусть дана система линейных уравнений

 

           (1)

     Коэффициенты a11,12,..., a1n, ... , an1 , b2 , ... , bn   считаются заданными.

Вектор - строка íx1  , x2  , ... , xn  ý - называется решением системы (1), если при подстановке этих чисел вместо переменных все уравнения системы (1) обращаются в верное равенство.

       Определитель n-го порядка DAê=ça ij  ç, составленный из коэффициентов при неизвестных, называется определителем системы (1). В зависимости от определителя системы (1) различают следующие случаи:

         a) если D¹0, то система (1) имеет единственное решение, которое может быть найдено методом Гаусса;

         б) если D=0, то система (1) либо имеет бесконечное множество решений, либо несовместна, т.е. решений нет.

 

 

1. Рассмотрим систему 3-х линейных уравнений с тремя неизвестными.

 

 

         (2).

 

 

      Метод Гаусса решения системы (2) состоит в следующем:

 Разделим все члены первого уравнения на , а затем, умножив полученное уравнение на , вычтем его соответственно из второго и третьего уравнений системы (2).  Тогда из второго и третьего уравнений неизвестное  будет исключено, и получиться система вида:

 

             (3)

 

  Теперь разделим второе уравнение системы (3) на, умножим полученное уравнение на  и вычтем из третьего уравнения. Тогда из третьего уравнения неизвестное  будет исключено и получиться система треугольного вида:

 

           (4)

 

Из последнего уравнения системы (4) находим , подставляя найденное значение в первое уравнение, находим .

 

Пример:

 

Методом Гаусса решить систему:

                                            

 

Решение:   разделив уравнение (а) на 2, получим систему

 

Вычтем из уравнения (b) уравнение , умноженное на 3, а из уравнения (c) -

уравнение , умноженное на 4.

 

 

Разделив уравнение () на -2,5 , получим:

Вычтем из уравнения () уравнение , умноженное на -3:

Из уравнения находим Z=-2;  подставив это значение в уравнение , получим Y=0,2-0,4Z=0,2-0,4(-2)=1;  наконец, подставив значение Z=-2  и  Y=1 в уравнение(a1), находим

X=0,5-0,5Y-Z=0,5-0,5*1 - (-2)=2.

 

Итак, получаем ответ X=2, Y=1, Z=-2 . [3]

 

Проверка:

 

 

 

7. Итерационные процедуры и их сходимость к решению.

Итерационные методы дают приближенное решение систем путем бесконечных сходящихся процессов.

К итерационным методам относятся:

·        метод последовательных приближений (метод Якоби);

·         метод простой итерации;

·         метод Гаусса - Зейделя;

·         метод релаксации.

Итерационные методы

Итак, требуется решить уравнение

\begin{displaymath}
\mbox{${\rm A}$}\mbox{\boldmath${\rm\bf f}$} = \mbox{\boldmath${\rm\bf g}$} ,
\end{displaymath}

(1)


где $\mbox{${\rm A}$}$- квадратная $n \times n$матрица с элементами $a_{ij}$, $\mbox{\boldmath${\rm\bf f}$}=(f_1,\ldots ,f_n)$, $\mbox{\boldmath${\rm\bf g}$}=(g_1,\ldots
,g_n)$ -- $n$-мерные векторы. Итерационные методы решения системы (1) позволяют строить последовательность приближений (итераций) $\{\mbox{\boldmath${\rm\bf f}$}^k\}^\infty_{k=0}$. Если эта последовательность имеет предел, то предел называется решением системы (1):

\begin{displaymath}
\mbox{\boldmath ${\rm\bf f}$}=\lim_{k\to\infty}\mbox{\boldmath ${\rm\bf f}$}^k .
\end{displaymath}


Очередное приближение строится с помощью рекуррентной формулы

\begin{displaymath}
\mbox{\boldmath ${\rm\bf f}$}^{k+1}=\mbox{\boldmath ${\rm\bf...
...th ${\rm\bf f}$}^0,\ldots ,\mbox{\boldmath ${\rm\bf f}$}^k) ,
\end{displaymath}


где $k$- номер итерации.

 

Преимущественно используется простейшая рекуррентная формула

\begin{displaymath}
\mbox{\boldmath ${\rm\bf f}$}^{k+1}=\mbox{${\rm B}$}\mbox{\boldmath ${\rm\bf f}$}^k+\mbox{\boldmath ${\rm\bf h}$} ,
\end{displaymath}


где $\mbox{${\rm B}$}$- квадратная $n \times n$матрица, а $\mbox{\boldmath${\rm\bf h}$}$ -- $n$-мерный вектор.

где B – квадратная матрица, а hn-мерный вектор 

Для организации счета по такой формуле требуется задание некоего начального приближения $\mbox{\boldmath${\rm\bf f}$}^0$. Вид матрицы $\mbox{${\rm B}$}$и вектора $\mbox{\boldmath${\rm\bf h}$}$определяет тот или иной итерационный метод. Рассмотрим наиболее часто встречающиеся методы.


Метод последовательных приближений (метод Якоби)

Исходная система (1) преобразуется к виду

\begin{displaymath}
\mbox{${\rm A}$}\mbox{\boldmath ${\rm\bf f}$}=(\mbox{${\rm A...
...\mbox{\boldmath ${\rm\bf f}$}=\mbox{\boldmath ${\rm\bf g}$} ,
\end{displaymath}

где $\mbox{${\rm I}$}$- единичная матрица, и далее,

\begin{displaymath}
\mbox{\boldmath ${\rm\bf f}$}=(\mbox{${\rm I}$}-\mbox{${\rm ...
...\mbox{\boldmath ${\rm\bf f}$}+\mbox{\boldmath ${\rm\bf g}$} .
\end{displaymath}


Счет организуется по формуле

\begin{displaymath}
\mbox{\boldmath${\rm\bf f}$}^{k+1}=(\mbox{${\rm I}$}-\mbox{$...
...\mbox{\boldmath${\rm\bf f}$}^k+\mbox{\boldmath${\rm\bf g}$} .
\end{displaymath}

(2)


Таким образом $\mbox{${\rm B}$}=\mbox{${\rm I}$}-\mbox{${\rm A}$}$, a $\mbox{\boldmath${\rm\bf h}$}=\mbox{\boldmath${\rm\bf g}$}$.


Метод простой итерации

Представим матрицу $\mbox{${\rm A}$}$ в виде суммы

\begin{displaymath}
\mbox{${\rm A}$}=\mbox{${\rm L}$}+\mbox{${\rm D}$}+\mbox{${\rm R}$} ,
\end{displaymath}

(3)


где $\mbox{${\rm D}$}$- диагональная матрица с элементами $a_{ii}$, $\mbox{${\rm L}$}$и $\mbox{${\rm R}$}$ - нижняя и верхняя треугольные матрицы, состоящие из соответствующих элементов исходной матрицы $\mbox{${\rm A}$}$.

Система (1) подвергается далее следующему преобразованию:

\begin{displaymath}
\mbox{${\rm A}$}\mbox{\boldmath ${\rm\bf f}$}=(\mbox{${\rm A...
...\mbox{\boldmath ${\rm\bf f}$}=\mbox{\boldmath ${\rm\bf g}$} ,
\end{displaymath}


откуда получаем

\begin{displaymath}
\mbox{\boldmath ${\rm\bf f}$}^{k+1}=\mbox{${\rm D}$}^{-1}(\m...
...f f}$}^k+\mbox{${\rm D}$}^{-1}\mbox{\boldmath ${\rm\bf g}$} ,
\end{displaymath}


\begin{displaymath}
\mbox{${\rm B}$}=\mbox{${\rm D}$}^{-1}(\mbox{${\rm D}$}-\mbo...
...m\bf h}$}=\mbox{${\rm D}$}^{-1}\mbox{\boldmath${\rm\bf g}$} .
\end{displaymath}

(4)


Матрица $\mbox{${\rm D}$}^{-1}$, обратная диагональной матрице $\mbox{${\rm D}$}$, вычисляется просто, поскольку также является диагональной с элементами $1/a_{ii}$.


Метод Гаусса-Зейделя

Снова запишем матрицу в виде (3), а систему (1) преобразуем к виду

\begin{displaymath}
\mbox{${\rm A}$}\mbox{\boldmath ${\rm\bf f}$}=(\mbox{${\rm L...
...\mbox{\boldmath ${\rm\bf f}$}=\mbox{\boldmath ${\rm\bf g}$} .
\end{displaymath}


Отсюда получаем рекуррентную формулу

\begin{displaymath}
\mbox{\boldmath ${\rm\bf f}$}^{k+1}=-(\mbox{${\rm L}$}+\mbox...
...rm L}$}+\mbox{${\rm D}$})^{-1}\mbox{\boldmath ${\rm\bf g}$} ,
\end{displaymath}


\begin{displaymath}
\mbox{${\rm B}$}=-(\mbox{${\rm L}$}+\mbox{${\rm D}$})^{-1}\m...
...rm L}$}+\mbox{${\rm D}$})^{-1}\mbox{\boldmath ${\rm\bf g}$} .
\end{displaymath}


Метод последовательной релаксации

Пусть $\tau>0$ - число, которое мы будем называть параметром релаксации. Умножим на это число систему (1)

\begin{displaymath}
\tau\mbox{${\rm A}$}\mbox{\boldmath ${\rm\bf f}$}=\tau\mbox{\boldmath ${\rm\bf g}$}
\end{displaymath}


и преобразуем ее следующим образом:

\begin{displaymath}
\tau\mbox{${\rm A}$}\mbox{\boldmath ${\rm\bf f}$}=(\tau\mbox...
...box{${\rm D}$}-\mbox{${\rm D}$})\mbox{\boldmath ${\rm\bf f}$}=
\end{displaymath}\begin{displaymath}
=(\tau\mbox{${\rm L}$}+\mbox{${\rm D}$})\mbox{\boldmath ${\r...
...x{\boldmath ${\rm\bf f}$}=\tau\mbox{\boldmath ${\rm\bf g}$} .
\end{displaymath}

В результате получаем рекуррентную формулу

\begin{displaymath}
\mbox{\boldmath ${\rm\bf f}$}^{k+1}=-(\tau\mbox{${\rm L}$}+\...
...}$}+\mbox{${\rm D}$})^{-1}\tau\mbox{\boldmath ${\rm\bf g}$} ,
\end{displaymath}


\begin{displaymath}
\mbox{${\rm B}$}=-(\tau\mbox{${\rm L}$}+\mbox{${\rm D}$})^{-...
...}$}+\mbox{${\rm D}$})^{-1}\tau\mbox{\boldmath ${\rm\bf g}$} .
\end{displaymath}


Параметр релаксации используется для настройки метода на максимальную скорость сходимости и обычно подбирается эмпирически. При этом $\tau\in(0,2)$. Если $\tau>1$, получаем метод верхней релаксации, если $\tau<1$ - метод нижней релаксации. [1]


8. Понятие о плохо обусловленных системах.

Под обусловленностью вычислительной задачи понимают чувствительность ее решения к малым погрешностям входных данных.

Пусть установлено неравенство image002.gif(382 bytes), где image004.gif(251 bytes) - относительная погрешность входных данных, а image006.gif(256 bytes)- относительная погрешность решения. Тогда image008.gif(195 bytes)- называется абсолютным числом обусловленности задачи. Если же установлено неравенство image010 (382 bytes) между относительными погрешностями данных и решения, то image012 (195 bytes)называют относительным числом обусловленности задачи.  

Обычно под числом обусловленности image014.gif (179 bytes) понимают относительное число обусловленности. Если image016.gif(220 bytes), то задачу называют плохо обусловленной.

Обусловленность задачи нахождения корня. Пусть image018.gif(181 bytes) v корень, подлежащий определению. Будем считать, что входными данными для задачи вычисления корня являются значения функции image020.gif(216 bytes). Так как image021gif (216 bytes)v вычисляется приближенно, то обозначим функцию, полученную в действительности через image023.gif(230 bytes). Предположим, что в малой окрестности корня выполняется неравенство:

image025.gif (525 bytes).

Для близких к image026.gif (181 bytes) значений image028.gif (178 bytes)справедливо равенство image30.gif (497 bytes), следовательно, image032.gif (595 bytes). Это означает, что число обусловленности задачи нахождения корня равно image034.gif (403 bytes). Из последней формулы следует, что чем меньше значение производной функции в точке корня, тем задача хуже обусловлена. В частности, задача нахождения кратного корня имеет число обусловленности - бесконечность.

 Интервал неопределенности корня. Если функция image035.gif (216 bytes) непрерывна, то найдется такая малая окрестность image037.gif (293 bytes) корня image038.gif (181 bytes), имеющая радиус image040.gif (174 bytes), в которой выполнено неравенство image042.gif (291 byes). Это означает, что image044.gif (187 bytes)image045.gif (293 bytes)знак вычисленного значения image046.gif (230 bytes), вообще говоря не обязан совпадать со знаком image047.gif (216 bytes)и, следовательно, становится невозможным определить, какое именно значение image049.gif (174 bytes)из интервала image050.gif (293 bytes)обращает функцию image052.gifв нуль. Этот интервал называется интервалом неопределенности корня. Очевидно, что радиус интервала неопределенности для простого корня равен image054.gif (631.gif). Аналогично можно показать, что для кратного корня image056.gif (525 bytes). Это означает, что для простого корня радиус интервала неопределенности прямо пропорционален погрешности вычисления функции image058.gif (256 bytes), а для кратного корня image060.gif (357 bytes).

Пример. Теоретическая оценка радиуса интервала неопределенности корня.

Пусть image062.gif (319 bytes).

Корень уравнения простой и равен image063.gif (181 bytes)= -0.34729635533861.

Тогда image065.gif (302 bytes)и image067.gif (301 bytes).

Если image069.gif (340 bytes), то image071.gif (258 bytes). Это означает, что найти корень с точностью меньшей, чем радиус интервала неопределенности, не удастся.

Применение метода Ньютона для нахождения кратного корня. Метод Ньютона для случая кратного корня обладает лишь линейной скоростью сходимости. Чтобы сохранить квадратичную сходимость его модифицируют следующим образом:

image073.gif (694 bytes), где image075.gif (184 bytes)- кратность корня.

 Как правило, значение image076.gif (184 bytes)v неизвестно. Используя метод Ньютона, можно узнать кратность корня. Для этого будем задавать значения image077.gif (184 bytes)= 1,2,3 и вычислять значение корня с заданной точностью , одновременно подсчитывая количество итераций для каждого значения image078.gif (184 bytes). При некотором значении image079.gif (184 bytes)число итераций будет минимальным. Это значение image080.gif (184 bytes)и есть кратность корня.

 

9. Регуляция систем с большим количеством обусловленности.

Известно, с какими трудностями связано решение так называемых плохо обусловленных систем линейных алгебраических уравнений: малым изменениям пра­вых частей таких систем могут отвечать большие (выходящие за допустимые пределы) изменения решения.

Рассмотрим систему уравнений

                                                            Аz=u,                                                              (1)

где А — матрица с элементами aij, А ={aij}, z — иско­мый вектор с координатами zj , z={zj}, и — известный вектор с координатами иi ,u= {ui}, i, j =1, 2, ..., п.

Система (1) называется вырожденной, если опреде­литель системы равен нулю, detA = 0. В этом случае матрица А имеет равные нулю собственные значения. У плохо обусловленных систем такого вида матрица А имеет близкие к нулю собственные значения.

Если вычисления производятся с конечной точностью, то в ряде случаев не представляется возможным уста­новить, является ли заданная система уравнений вырож­денной или плохо обусловленной. Таким образом, плохо обусловленные и вырожденные системы могут быть не­различимыми в рамках заданной точности. Очевидно, такая ситуация имеет место в случаях, когда матрица А имеет достаточно близкие к нулю собственные значения.

В практических задачах часто правая часть и и эле­менты матрицы А, т. е. коэффициенты системы (1), известны приближенно. В этих случаях вместо системы (2) мы имеем дело с некоторой другой системой Az=и такой, что ||A-A||<=h, ||u-u||<= d, где смысл норм обычно определяется характером задачи. Имея вместо матрицы А матрицу A, мы тем более не можем высказать определенного суждения о вырожденности или невырожденности системы (1).

В этих случаях о точной системе Аz=u, решение которой надо определить, нам известно лишь то, что для матрицы А и правой части и выполняются неравенства ||A-A||<=h, ||u-u||<= d. Но систем с такими исходными данными (А, и) бесконечно много, и в рамках извест­ного нам уровня погрешности они неразличимы. Поскольку вместо точной системы (1) мы имеем приближенную систему Аz=и, то речь может идти лишь о нахождении приближенного решения. Но приближенная система Аz может быть неразрешимой. Возникает вопрос: что надо понимать под приближенным решением систе­мы (1) в описанной ситуации?

Среди «возможных точных систем» могут быть и вы­рожденные. Если они разрешимы, то имеют бесконечно много решений. О приближенном нахождении какого из них должна идти речь?

Таким образом, в большом числе случаев мы должны рассматривать целый класс неразличимых между собой (в рамках заданного уровня погрешности) систем урав­нений, среди которых могут быть и вырожденные, и неразрешимые. Методы построения приближенных реше­ний систем этого класса должны быть одними и теми же, общими. Эти решения должны быть устойчивыми к малым изменениям исходных данных (1).

В основе построения таких методов лежит идея «от­бора». Отбор можно осуществлять с помощью специальных, заранее задаваемых функционалов W[z], входящих в постановку задачи.

Неотрицательный функционал W[z], определенный на всюду плотном в F подмножестве F1 множества F, называется стабилизирующим функционалом, если:

а) элемент zT принадлежит его области определения;

б) для всякого числа d>0 множество F1,d элементов z из F1 , для которых W[ z ]<=d, компактно на F.

 

Итак, рассмотрим произвольную систему линейных алгебраических уравнений (короче — СЛАУ)

Аz =u,                                                      (3)

в которой z и u—векторы, z=(z1, z2, ...,zn) ÎRn, и=(u1,u2, ...,un) ÎRm, А—матрица с элементами aij, А = {aij}, где j =1, 2, ..., n; i= 1, 2, ..., т, и число п не обязано быть равным числу т.

Эта система может быть однозначно разрешимой, вы­рожденной (и иметь бесконечно много решений) и не­разрешимой.

Псевдорешением системы (3) называют вектор z, минимизирующий невязку || Azu || на всем пространстве Rn. Система (3) может иметь не одно псевдоре­шение. Пусть FA есть совокупность всех ее псевдореше­ний и z1 — некоторый фиксированный вектор из Rn, оп­ределяемый обычно постановкой задачи.

Нормальным относительно вектора z1 решением си­стемы (3) будем называть псевдорешение z0 с ми­нимальной нормой || zz1 ||, т. е. такое, что

|| z0z1 || =

 

Здесь . В дальнейшем для простоты записи будем считать z1= 0 и нормальное относительно вектора z1=0 решение называть просто нормальным ре­шением.

Для любой системы вида (3)  нормальное решение существует и единст­венно.

 

Замечание 1. Нормальное решение z° системы (3) можно определить также как псевдорешение, минимизирующее заданную положительно определенную квадратичную форму относительно координат вектора zz1. Все излагаемые ниже результаты остаются при этом справедливыми.

 

Замечание 2. Пусть ранг матрицы А вырожден­ной системы (1) равен r < n и zr+1,zr+2, … , zn— базис линейного пространства NA, состоящего из элемен­тов z, для которых Аz=0, NA = {z; Аz= 0}. Решение z° системы (1), удовлетворяющее nr условиям ортогональности

                                 (z0z1, zS)= 0,   S= r + 1, r + 2, .. ,n,                      (4)

определяется однозначно и совпадает с нормальным ре­шением.

 

Нетрудно видеть, что задача нахождения нормаль­ного решения системы (3) является некорректно поставленной. В самом деле, пусть А — симметричная матрица. Если она невырожденная, то ортогональным преобразованием

z = Vz*, u = Vu*

ее можно привести к диагональному виду и преобразо­ванная система будет иметь вид

lizi*=ui* , i= 1, 2,. .., п,

где li — собственные значения матрицы А.

Если симметричная матрица А — невырожденная и имеет ранг r, то nr  ее собственных значений равны нулю. Пусть

li¹0 для i=1, 2, ..., r;

и

li=0 для i=r+1,r+2, …, n.

Полагаем, что система (3) разрешима. При этом ui*= 0 для i =r + 1, ..., n.

Пусть «исходные данные» системы и и) заданы с погрешностью, т. е. вместо А и и заданы их прибли­жения А и u:

 || AA ||<=h,  ||uu||<=d . При этом           

                                                        (5)

Пусть li собственные значения матрицы А. Извест­но, что они непрерывно зависят от А в норме (5). Следовательно, собственные значения lr+1 , lr+2, …,ln могут быть сколь угодно малыми при достаточно малом h.

Если они не равны нулю, то

 

             zi*=.

Таким образом, найдутся возмущения системы в пре­делах любой достаточно малой погрешности А и и, для которых некоторые zi* будут принимать любые наперед заданные значения. Это означает, что задача нахожде­ния нормального решения системы (3) является неустойчивой.

 

Заключение

В этой теме мы рассмотрели: моделирование эпидемий, методы анализа аналитической модели, итерационные методы,  точные методы решения систем линейных алгебраических уравнений.

В следующей теме мы узнаем, что такое имитационное моделирование, его преимущества и недостатки, этапы разработки имитационного моделирования. 

Вопросы для самоконтроля:

 

1.      Расскажите о методах исследования аналитической модели.

2.      Какова общая процедура решения уравнений?

3.      Постройте графики итерационных методов хорд и касательных.

4.      В чем отличие метода Ньютона от метода хорд?

5.      В каком случае сходится итерационный процесс?

6.      Какие методы относятся к точным методам решения решения систем линейных алгебраических уравнений?

7.      Какие методы относятся к итерационным?

8.      Что понимают под обусловленностью вычислительной задачи?

 

Литература:

1.      Белевич М.Ю. Методы решения систем линейных алгебраических уравнений // www.pages.rshu.ru/mamop/node50.html.

2.      Заболотский В.П., Оводенко А.А., Степанов А.Г. Аналитическое моделирование // www.allmath.ru/appliedmath/operations/operations3/operations.htm.

3.      Ханова А.А. Численное решение уравнений и систем уравнений // www.exponenta.ru/educat/systemat/hanova/equation/nonlinear/nonlinear2.asp