Современные интерьеры зданий Эмоциональный потенциал архитектуры О развитии пространства О масштабе и образе Форма, материал, цвет Творчество в проектировании О компонентах интерьера

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

$\displaystyle x_{i+1}=x_i-\dfrac{1}{f'(x_i)}f(x_i)$(9.1)
 


(сравните с формулой метода одной касательной). Этот метод называется методом касательных, или методом Ньютона. Действительно, последовательные приближения метода Ньютона сходятся гораздо быстрее, чем в общем методе итераций (скорость сходимости приближений в котором, напомним, та же, что у геометрической прогрессии со знаменателем $ {\gamma}$ при $ 0<{\gamma}<1$).

Поскольку для метода Ньютона Метод итераций

$\displaystyle {\varphi}(x)=x-\dfrac{f(x)}{f'(x)},$

то

$\displaystyle {\varphi}'(x)=1-\dfrac{(f'(x))^2-f(x)f''(x)}{(f'(x))^2}=
\dfrac{f(x)f''(x)}{(f(x))^2}.$

В точке $ x^*$ получаем $ {\varphi}'(x^*)=0$, так как $ f(x^*)=0$. Тем самым, в этом методе график $ y={\varphi}(x)$ пересекает прямую $ y=x$ в точности по горизонтали, что приводит к очень быстрой сходимости итераций к $ x^*$. Именно, имеет место оценка

$\displaystyle \vert x_{i+1}-x^*\vert\leqslant c\vert x_i-x^*\vert^2\leqslant \dfrac{1}{c}(c\vert x_0-x^*\vert)^{2^{i+1}},$(9.2)
 


где $ c$ -- некоторая постоянная (не зависящая от $ i$). Если начальное приближение $ x_0$ взято достаточно близко от корня $ x^*$, то можно взять $ c=\dfrac{1}{\vert x_0-x^*\vert}$.

Заметим, что по сравнению с общей оценкой метода итераций

$\displaystyle \vert x_{i+1}-x^*\vert\leqslant {\gamma}\vert x_i-x^*\vert,$

постоянная $ {\gamma}<1$ заменяется в оценке метода Ньютона (9.2) на стремящуюся к 0 величину $ c\vert x_i-x^*\vert$; отсюда и высокая скорость сходимости.

Скорость сходимости итераций, которая задаётся формулой (9.2), называется квадратичной. Квадратичная скорость сходимости означает, примерно говоря, что число верных знаков в приближённом значении $ x_i$ удваивается с каждой итерацией. Действительно, если $ c\approx1$, и $ \vert x_i-x^*\vert\approx10^{-n}$, то $ \vert x_{i+1}-x^*\vert\approx10^{-2n}$. Это и означает, что число верных знаков при переходе к следующему приближению возросло с $ n$ до $ 2n$, то есть удвоилось.

Геометрический смысл метода Ньютона состоит в том, что на каждом шаге мы строим касательную к графику $ y=f(x)$ в точке очередного последовательного приближения $ x_i$, а за следующее приближение $ x_{i+1}$ берём точку пересечения этой касательной с осью $ Ox$. Тем самым наклон прямой подстраивается на каждом шаге наилучшим образом (ведь кривизну графика, связанную с второй производной, мы не учитываем, и поэтому неизвестно, в какую сторону от касательной отклонится график).

Рис.9.13.Последовательные приближения метода Ньютона

Заметим, что по-другому идею метода Ньютона мы можем описать так: на каждом шаге вместо исходного уравнения $ f(x)=0$ мы решаем приближённое, линеаризованное в точке $ x_i$ уравнение

$\displaystyle f(x_i)+f'(x_i)(x-x_i)=0,$

в котором левая часть -- это многочлен Тейлора первого порядка для функции $ f(x)$ в точке $ x_i$, то есть линейная функция

$\displaystyle \ell_{x_i}(x)=f(x_i)+f'(x_i)(x-x_i).$

Решением линеаризованного уравнения $ \ell_{x_i}(x)=0$ служит следующее приближение $ x_{i+1}$, в то время как решением исходного точного уравнения $ f(x)=0$ служит искомый корень $ x^*$.

Идея замены точной (но сложной) задачи последовательностью более простых линеаризованных задач весьма продуктивна в приближённых методах; например, такая идея даёт эффективный способ решения многомерных задач с ограничениями (метод Франка - Вулфа в нелинейном программировании, см., например, [Киселёв В.Ю., Экономико-математические методы и модели. -- Иваново: изд. ИГЭУ, 1998]).

 Определение. Вершина w графа D (или орграфа) называется достижимой из вершины v, если либо w=v, либо существует путь из v в w(маршрут, соединяющий v и w).

 

 Определение. Граф (орграф) называется связным, если для любых двух его вершин существует маршрут (путь), который их связывает. Орграф называется односторонне связным, если если для любых двух его вершин по крайней мере одна достижима из другой.

 

 Определение. Псевдографом D(V, X), ассоциированным с ориентированным псевдографом, называется псевдограф G(V, X0) в котором Х0 получается из Х заменой всех упорядоченных пар (v, w) на неупорядоченные пары (v, w).

 

 Определение. Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф

 

Эйлеровы и гамильтоновы графы.

[an error occurred while processing this directive]  

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

 

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

 

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

 

 Определение. Цикл (цепь) в псевдографе G называется гамильтоновым, если он проходит через каждую вершину псевдографа G ровно один раз.

Пример.

 

 

 

 


 - в графе есть и эйлеровый и гамильтонов циклы

 

 

 

 

 

 

 

 

 


 - в графе есть эйлеров цикл, но нет гамильтонова

 - в графе есть гамильтонов, но нет эйлерова цикла

 - в графе нет ни эйлерова, ни гамильтонова цикла

 Граф G называется полным, если если каждая его вершина смежна со всеми остальными вершинами. В полном графе всегда существуют гамильтоновы цмклы.

 Также необходимым условием существования гамильтонова цикла явояется связность графа.

Интегрирование биноминальных дифференциалов.

 Так называются дифференциалы вида хm(a + bxn)p dx, где а, b – постоянные, отличные от нуля, m, n, p – рациональные числа.

 Первообразная для функции хm(a + bxn)p является элементарной функцией в следующих трех случаях: а) р – целое, б) - целое, в) - целое;

 а) если р – целое, то полагают x = z где N – общий знаменатель дробей m и n.

Мащиностроительное черчение