По поиску собственных значений и векторов матриц

Пусть рассматривается некий процесс, зависящий от одного параметра х и описываемый функцией y=f(x). Поставим задачу: определить такие значения параметра х, равные х*, которые вызывают остановку процесса, то есть выполнение условия:

f(x)=0                                                            (4.1)

Теорема о существовании нуля непрерывной функции: Если функция f(x) непрерывна на отрезке [a,b] и принимает на его концах значения разных знаков, то на этом отрезке существует по крайней мере один корень уравнения (3.1).

Пусть известно, что на [a,b] существует единственный корень уравнения (1). Потребуем, чтобы функция:

1) была непрерывна на [a,b] вместе со своими производными f¢(x) и f²(x);

2) в точках a и b функция имеет разные знаки, т.е. f(a)×f(b)<0;

3) производные f¢(x), f²(x) – сохраняют знак на всем [a,b], т.е. функция должна быть строго монотонной на [a,b].

Метод бисекции (половинного деления). Суть метода: [a,b] делится на два равных отрезка [a,c] и [c,b]. Рассчитывается значение функции в точке с. Если f(c)¹0, то из двух отрезков [a,c] и [c,b] выбирается тот, в котором функция f(x) имеет разные знаки на концах и обозначается за [a₁,b₁]. Отрезок [a₁,b₁] разбивается на два равных отрезка точкой с₁.Считается значение f(c₁). Если оно не равно нулю, то из двух отрезков [a₁ ,c₁] и [c₁,b₁] выбирается тот, в котором функция f(x) имеет разные знаки на концах и обозначается за [a₂,b₂]. Продолжая аналогичные действия, в результате строится последовательность отрезков [a_n,b_n]. На n-ом шаге процесса получаем:

a_n £ х* £ b_n.                                           (4.2)

Это двойное неравенство показывает, что число a_n определяет х* с недостатком, а число b_n – с избытком. За решение уравнения (4.1) принимается значение x*=(a_n + b_n)/2 при условии, что

D_n < e                                                     (4.3)

где D_n = |b_n – a_n|, а e - заданная точность.

Очевидно, что скорость сходимости метода половинного деления будет равна ½.

Метод итераций.Предположим, что уравнение (3.1) можно переписать в виде:

x=j(x)                                               (4.4)

Возьмем произвольное значение х₀ из области определения функции j(x) и будем строить последовательность чисел {x_n}, определенных с помощью рекуррентной формулы

x_n+1 = j(x_n), n=0, 1, 2, …                                 (4.5)

Последовательность {x_n} называется итерационной последовательностью.

Точность найденного решения определяется формулой (4.3):

D_n = |x_n – x_n-1| < e                             (4.6)

где e - заданная точность.

Метод хорд. Будем полагать, что функция f(x) дважды дифференцируема на [a,b] функция.

Метод хорд требует, чтобы один конец отрезка [a,b], был неподвижен. Условие неподвижности точки:

f ”(x_н) × f(x_н) > 0                               (4.7)

Расчетная формула для определения n-ого приближения:

                                (4.8)

При выполнении условия (4.6) за решение принимается х*=x_n.

Метод касательных (метод Ньютона). Будем полагать, что функция f(x) – это дважды дифференцируемая на [a,b] функция.

Метод заключается в следующем: из точки, для которой выполняется условие (4.7) испускается касательная к кривой y=f(x), которая пересекает ее в точке х₁ – эта точка станет первым приближением к корню х*, затем вновь проводим касательную к кривой в точке (х₁,f(x₁)) – получим х₂ и т.д.

b f(b)×f²(b)>0   a х1 х2

Формула определения абсцисс точек пересечения касательных с осью Ох имеет вид: (4.9) Точка xnбудет являться корнем уравнения (4.1) при выполнении (4.6).  Геометрическое представление метода показано на рисунке:

Комбинированный метод хорд и касательных.Для ускорения сходимости используют комбинированный метод хорд и касательных. Здесь одновременно из точки (b,f(b)) проводят касательную, а из точки (a,f(a)) – хорду. Получается новый интервал (a₁, b₁) и процедура повторяется до выполнения условия

                                   (4.10)

В это)м случае за «истинное» решение уравнения (4.1) можно принять значение

                                                   (4. 11)

Пример 4.1.

Найти решение уравнения f(x)=x-cos(x)=0 на отрезке [0,1] с ε=0, 01 с помощью каждого описанного метода.

Решение:

Для этой функции на указанном отрезке выполняются следующие условия:

f’>0, f’’>0.

Следующая таблица показывает работу метода половинного деления:

Как видно из таблицы на 7 -ой итерации получен корень уравнения х=0,738. Точность равна 0,01. (для определенности оставим в значении корня третий знак после запятой)

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

n > log₂ ((b-a)/e)

где n – ближайшее большее целое число.

Следовательно, для нашей задачи: n > log₂ ((1-0)/0.01) = log₂100 = 6.64 , то есть n=7, что и видно из таблицы.

Последовательность вложенных сегментов имеет вид:

^-[0,1]⁺ É ^-[0.5,1]⁺ É ^-[0.5,0.75]⁺ É ^-[0.625,0.75]⁺ É ^-[0.688,0.75]⁺ É ^-[0.719,0.75]⁺ É ^-[0.734,0.75]⁺ É ^-[0.734,0.742]⁺ É 0.738

Верхние индексы, стоящие слева и справа от отрезка, показывают знак функции соответственно в левом и правом конце интервала.