F'(x) > 0

0 f'(x) > 0

f''(x) >

0 f''(x) < 0

f(a) a x

3) 4)

f'(x)

<0 f'(x) <0

f''(x)

<0 f''(x) > 0

 (2.1)

x₁(x₁,f(x₁))

b – неподвижный конец отрезка.

Для случаев 1), 3)

Для случаев 2), 4)

Можем ввести некоторую с:

(2.2)

(2.3)

Алгоритм:

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

2)  Находим первое приближение к корню по формуле (2.1)

3)  Находим первое приближение к корню по формуле (2.2) до тех пор, пока модуль разности двух последних приближений не станет меньше заданной точности. В этом случае, значением корня является последнее приближение.

МЕТОД КАСАТЕЛЬНЫХ

 

Дано: 1) f(x) C''[a, b];

2) f(a)*f(b) < 0;

3) f'(x) и f''(x) знакопостоянны на [a, b];

4) ε, чтобы решить уравнение f(x)=0

 

т. х₀

y=f(x₀)+f'(x₀)(x-x₀) –

уравнение касательной

a x₂  x₁ b

y=f(b)+f’(b)*(x-b)

(x₁,0) : 0= f(b)+ f’(b)(x₁-b)

x₁=

x₂=

x_n+1= (2.4)

Второй подход (метод Ньютона):

-приближение

0 = f() = f(x_n+h_n) ≈ f(x_n)+f'(x_n)*h_n

x₀ = начальное приближение (2.5)

Алгоритм:

1)  По формуле (2.5) находим первое приближение к корню х₀ (начальное)

2)  По формуле (2.4) находим последующее приближение к корню до тех пор, пока модуль разности двух последних приближений не станет заданной точности. В этом случае корень равен последнему приближению.

МЕТОД ИТЕРАЦИЙ

Дано: 1) f(x)C''[a,b]

 2)f(a)*f(b)<0

 3)f'(x) знакопостоянна

 4)ε, f(x)=0

Уравнение f(x)=0 заменяется уравнением вида x=φ(x)

φ(x)=x-f(x)*C  (2.6)

Пока |x_n+1-x_n|<ε

φ' >0

Cтроим последователь  

Выбираем

Находим значение функции

x₂= φ(x₁), x₃= φ(x₂)

x_n+1= φ(x_n) (2.7)

Точка ε, для которой выполняется ε=f(ε), называется неподвижной точкой метода итераций. Очевидно, что эта точка является корнем уравнения f(x)=0.

φ(ε) ε -f(x)* ε

0 f(ε)*C

f(ε) 0

Достаточное условие: для того, чтобы метод итераций сходился достаточно чтобы:

1) φ(x) (2.8) - Функция является непрерывной и дифференцируемой на [a,b].

2) φ(x) значения  - является необходимым условием

3) |φ(x)|<1 для всех

Константа С в формуле(2.6) подбирается таким образом, чтобы функция

φ(x) удовлетворяла условиям сходимости метода итераций.

Скорость сходимости метода Ньютона (касательных) выше сходимости метода секущих (хорд).

ЛЕКЦИЯ №3

МЕТОДЫ РЕШЕНИЯ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

 

Общий вид алгебраического уравнения:

а₀хⁿ+ а₁хⁿ⁺¹+…+ а_n-1х+a_n=0, a₀0 (3.1)

n=1: а₀х+a₁=0, x=

n=2: а₀х²+a₁x+a₂=0, x_1,2=

Алгебраическое уравнение n- степени имеет ровно n корней.

Теорема Виета (обобщенная):

xⁿ+x^n-1+…+x+=0

x₁+x₂+…+x_n=-; (3.2)

x₁x₂+x₁x₃+…+x_n-1x_n=;

x₁x₂x₃…x_n=(-1);

Пусть все корни уравнения (3.1) действительны, различны и удовлетворяют соотношениям:

|x₁|>>|x₂|>>…>>|x_n|  (3.3)

Преобразуем:

x₁(1++…+)=  x₁=-; (3.4)

Подставим (3.4) : х₂=- продолжая получим общую формулу

х_k=-, k=1,n (3.5)

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

y_i=-x_i^m

b₀yⁿ + b₁y^n-1+…+ b_n-1y+b_n=0 (3.6)

|x₁|>|x₂|>…>|x_n|

Решив уравнение (3.6), корни которого являются отдельными, получим уравнения y₁…y_n

, i=2,n

Значит |y_i-1|>>|x_i|

МЕТОД ЛОБАЧЕВСКОГО

 

Для отделения корней Лобачевский предложил метод квадратирования - способ построения по исходному уравнению нового уравнения, кони которого связаны с корнями исходного следующим образом:

y_i=-x_i² (3.7)

Процедура выполнения многократна, пока не достигнем серьёзной разницы модуля разности корней

b₀^(m)yⁿ + b₁^(m)y^n-1+…+ b_n-1^(m)y+ b_n^(m)=0 (3.8)

Пусть уравнение (3.8) получено в результате m-го шага квадрирования.

m=1 b₀⁽¹⁾=a₀², b₁⁽¹⁾= a₁²=2 a₀ a₂

b_k⁽¹⁾=a_k²-2a_k-1a_k+1+2a_k-2a_k+2….,k=0,n

При получении b_k коэффициента , который рассчитывается как квадрат соответствующего коэффициента a_k минус удвоенное произведение соседних коэффициентов с a_kплюс удвоенное произведение следующей пары соседей , чередуя знаки, пока в число соседних коэффициентов не попадут а₀ и а_n.

m>1b₀^(m)=( b₀^(m-1))², b₁^(m)=( b₁^(m-1))²-2b₀^(m-1)b₂^(m-1) (3.9)

b_k^(m)=( b₀^(m-1))²-2b_k-1^(m-1)b_k-1^(m-1)+2b_k-2^(m-1)b_k+2^(m-1)

 

Критерий остановки: b_k^(m)≈( b₀^(m-1))², k=0,n (3.10)

Получим корень: y_i^(m)=-x_i², i=1,n (3.11)

(3.11)-связь корней, полученных на m-шаге процесса квадрирования с корнями исходного уравнения.

y_i на m-шаге : , отсюда

 , i=1,n (3.12)

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

Признак наличия кратных корней: один или несколько коэффициентов → к половине квадрата коэффициента предыдущего шага.

МЕТОДЫ РЕШЕНИЯ СИСТЕМ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

СЛАУ

Методы решения СЛАУ делятся на точные и приближенные. К точным методам относятся метод Гаусса, метод Крамера, метод обратной матрицы .

Существуют приближенные методы: метод итераций, Зейделя и т.д.

Общий вид СЛАУ:

(3.13)

Сколько переменных столько и ограничений на них.

пересечение прямых (точка)

пересечение плоскостей (прямая)

точка пересечения трех плоскостей

Т.о. геометрический смысл решения СЛАУ – точка пересечения гиперплоскостей в n-мерном пространстве.

Матрица :=А; B=; X=;

C_n*k*D_k*m=Z_n*m , A_n*n*B_n*1=X_n*1 AX=B (3.14)

ЛЕКЦИЯ №4

 

МЕТОД ГАУССА

 

Метод имеет прямой и обратный ход. Будем рассматривать процедуру прямого хода метода с выбором главного элемента. Главный элемент – максимальный по модулю элемент матрицы, выбранный на заданном множестве строк и столбцов.

1 шаг: Выбираем в матрице А максимальный элемент по всем строкам и столбцам. Путем перестановки строк и столбцов ставим этот элемент на место а₁₁. Теперь а₁₁- главный элемент.

А→А¹→А²→…→Аⁿ

Аⁿ должна будет содержать ниже главной диагонали все нули.

 , j =1,n ; b₁ =b₁/a₁₁

Получим систему вида

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

Получим А' х=В' и систему

Пусть а₂₂¹ – максимальный по модулю элемент матрицы А¹ по строкам i≥2 и столбцам j≥2. Если это не так, то добиваемся этого путем перестановки строк и столбцов.

А²:

В²: b₁²=b₁¹; b₂²=b₂¹/a₂₂¹; b_i²=b_i¹-b₂²-b₂²a_i2¹

Пусть а^к_к+1 максимальный по модулю элемент матрицы А^к, i≥k, j≥k.

Пусть на некотором шаге k<n элемент =0, матрица В^к имеет ∞ множество решений. Причем корни х₁,…х_к являются зависимыми, а корни х_к+1,….x_n – независимые.

Если хотя бы один элемент b_i^k при i≥k+1 ¹ 0, то решения у системы нет.

Если была получена матрица Аⁿ, то система имеет единственное решение.

Начинается обратный ход метода Гаусса.

МЕТОД КРАМЕРА

Определитель : det A=

det A==a₁₁a₂₂-a₁₂a₂₁

Минор H_ij элемента матрицы a_ij представляет собой определитель, полученный из матрицы А путем вычеркивания i cтроки и j столбца.

Алгебраическое дополнение А_ij элемента а_ij называется число, равное

 А_ij=(-1)^i+j*M_ij

Способы вычисления определителей

1.  Привести определитель к треугольному виду (ниже главной диагонали все элементы=0). Достичь этого можно путем вычитания (сложения) строк определителя, умноженных на некоторое число. При перестановки строк/столбцов знак определителя меняется на противоположный. Определитель треугольного вида равен произведению элементов главной диагонали.

2.  Рекуррентный способ основан на том, что определитель равен сумме произведений элементов строки/столбца на их алгебраические дополнения. Т.о. задача вычисления определителя n-го порядка сводится к вычислению n определителей n-1 порядка.

Наиболее целесообразно раскладывать определитель по той строке/столбцу, которая содержит максимальное количество нулей. Алгебраическое дополнение 0-го элемента можно не вычислять.

Пусть дана система уравнений вида Ах=В

Если определитель А=0, то система может решений не иметь, либо иметь бесконечное множество решений.

Если определитель А≠0, то корни системы могут быть найдены следующим образом.

Пусть А_к-матрица, полученная из матрицы А путем замен к-го столбца на матрицу-столбец В. Тогда решение .

  МЕТОД ОБРАТНОЙ МАТРИЦЫ

Пусть дана система Ах=В и detA≠0.

Умножим обе части системы на А^-1:

А^-1*Ах=А^-1*В→х=А^-1*В

 

Способы нахождения обратной матрицы:

1.  Способ основан на методе Гаусса.

Записать матрицу А, а рядом с ней единичную матрицу. Выполняя элементарные преобразования матрицы А, параллельно выполнять те же преобразования над единичной матрицей. Как только матрица А превратилась в единичную на месте исходной единичной матрицы будет обратная к матрице А.

2.  Через алгебраические дополнения.

Составить матрицу алгебраических дополнений, в которой на месте a_ij элементов будут находиться A_ij.

Разделить каждый элемент матрицы алгебраических дополнений на detA.

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