1.1. Отделение корней

В общем случае отделение корней уравнения f(x)=0 базируется на известной теореме, утверждающей, что если непрерывная функция f(x) на концах отрезка [a,b] имеет значения разных знаков, т.е. f(a)f(b)0, то в указан-ном промежутке содержится хотя бы один корень. Например, для уравнения f(x)= x³-6x+2=0 видим, что при x  f(x)>0, при x  f(x)<0, что уже свидетельствует о наличии хотя бы одного корня.

В общем случае выбирают некоторый диапазон, где могут обнаружиться корни, и осуществляют "прогулку" по этому диапазону с выбранным шагом h для обнаружения перемены знаков f(x), т.е. f(x)f(x+h)<0.

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

1.2. Уточнение корней методом половинного деления (дихотомии)

Рис. 1. Метод деления отрезка пополам

Самым простейшим из методов уточнения корней является метод половинного деления, или метод дихотомии, предназначенный для нахождения корней уравнений, представленных в виде f(x)=0.

Пусть непрерывная функция f(x) на концах отрезка [a,b] имеет значения разных знаков, т.е. f(a)f(b) 0 (рис. 1), тогда на отрезке имеется хотя бы один корень.

Возьмем середину отрезка с=(a+b)/2. Если f(a)f(c) 0, то корень явно принадлежит отрезку от a до (a+b)/2 и в противном случае от (a+b)/2 до b.

 

 

 

Рис. 2. Блок-схема метода половинного деления

Поэтому берем подходящий из этих отрезков, вычисляем значение функции в его середине и т.д. до тех пор, пока длина очередного отрезка не окажется меньше заданной предельной абсолютной погрешности (b-a)<.

Так как каждое очередное вычисление середины отрезка c и значения функции f(c) сужает интервал поиска вдвое, то при исходном отрезке [a,b] и предельной погрешности  количество вычислений n определяется условием (b-a)/2ⁿ<, или n~log₂((b-a)/). Например, при исходном единичном интервале и точности порядка 6 знаков (~ 10^-6) после десятичной точки достаточно провести 20 вычислений (итераций) значений функции.

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

БИЛЕТ 13

Рассматривается система Ax = b. Для применения итерационных методов система должна быть приведена к эквивалентному виду x=Bx+d. Затем выбирается начальное приближение к решению системы уравнений и находится последовательность приближений к корню. Для сходимости итерационного процесса достаточно, чтобы было выполнено условие . Критерий окончания итераций зависит от применяемого итерационного метода.

 

Метод Якоби.

Самый простой способ приведения системы к виду удобному для итерации состоит в следующем: из первого уравнения системы выразим неизвестное  x₁, из второго уравнения системы выразим  x₂, и т. д. В результате получим систему уравнений с матрицей B, в которой на главной диагонали стоят нулевые элементы, а остальные элементы вычисляются по формулам:

  ,    i, j = 1, 2, ... n.

Компоненты вектора d вычисляются по формулам:

  ,   i = 1, 2, ... n.

Расчетная формула метода простой итерации имеет вид

,

или в покоординатной форме записи выглядит так:

,  i = 1, 2, ... m.

Критерий окончания итераций в методе Якоби имеет вид:

,   где    .

Если   , то можно применять более простой критерий

окончания итераций

ПРИМЕР 1. Решение системы линейных уравнений методом Якоби.

Метод Зейделя.

Метод можно рассматривать как модификацию метода Якоби. Основная идея состоит в том, что при вычислении очередного (n+1)-го приближения к неизвестному  x_i при i >1 используют уже найденные (n+1)-е приближения к неизвестным  x₁, x₂, ..., x_{i - 1}, а не n-ое приближение, как в методе Якоби. Расчетная формула метода в покоординатной форме записи выглядит так:

,

 i = 1, 2, ... m.. Условия сходимости и критерий окончания итераций можно взять такими же как в методе Якоби.

ПРИМЕР 2. Решение систем линейных уравнений методом Зейделя.

 

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

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

Если A - симметричная и положительно определенная матрица, то систему уравнений часто приводят к эквивалентному виду:

x = x - (Ax - b),   - итерационный параметр.

Расчетная формула метода простой итерации в этом случае имеет вид:

x ⁽ⁿ⁺¹⁾ = x ⁿ -   (Ax ⁿ - b).

Здесь B = E -   A  и параметр   > 0 выбирают так, чтобы по возможности сделать минимальной величину   .

Пусть и - минимальное и максимальное собственные значения матрицы A. Оптимальным является выбор параметра   . В этом случае   принимает минимальное значение равное .

ПРИМЕР 3. Решение систем линейных уравнений методом простой итерации.

БИЛЕТ 15

: Безусловная одномерная оптимизация

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