Численные методы (стр. 2 из 3)

Константа С в формуле(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, то решения у системы нет.

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

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

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

Определитель : detA=

detA=

=a₁₁a₂₂-a₁₂a₂₁

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

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

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

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

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