12. Процедура сортировки одномерного массива.

Procedure Vybor(Var a:row; n:integer);

Var max,k,I,j:integer;

Begin

for i:=1 to n-1 do

begin

max:=a[i]; k:=I;

for j:=i+1 to n do

if a[j]> max

then begin max:=a[j]; k:=j

end

if k<>I then begin a[k]:= a[i];

a[i]:= max;

End;

13. Задача поиска корней уравнения. Метод половинного деления.

Этот метод позволяет на каждом шаге сузить отрезок, содержащий корень, вдвое, поскольку при делении отрезка пополам выбирается та его половина, на концах которого функция имеет значения разных знаков. Деление отрезка пополам продолжают до тех пор, пока не будет получен отрезок [a_n,b_n], дающий приближение корня с требуемой точностью (b_n-a_n,). Все такие методы приближенного решения уравнений называют итерационными методами (от латинского слова iteratio - повторение). Итерационные методы различаются формулами для вычисления приближений на каждом шаге итерационного процесса, при этом меняются характеристики метода, такие как скорость сходимости, простота реализации и т. д.

14. Алгоритм метода половинного деления.

+

15. Метод простой итерации для поиска корней. Геометрическая интерпретация.

+

Исходное уравнение f(x)=0 эквивалентными преобразованиями приводится к виду с выделением неизвестного в левой части, то есть

x=φ(x), (2)

где φ(x) – некоторая функция, связанная с исходной функцией f(x).

Такая форма записи уравнения позволяет, задаваясь начальным приближением x_0, получить следующее, первое приближение x₁=φ(x₀), далее получают второе приближение x₂=φ(x₁) и так далее x_n+1=φ(x_n)…. Последовательность {x_n}= x_0, x_1, x_2, …, x_n,… называется последовательностью итераций или приближений с начальным значением x_0.

Если функция φ(x) на [a,b] непрерывна и существует предел ξ = lim x_n при n→∞, то, переходя к пределу в равенстве x_n+1=φ(x_n), найдем, что при n→ ∞:

lim x_n+1=lim φ(x_n)=φ(lim x_n), то есть ξ=φ(ξ).

Следовательно, если последовательность приближений сходится, то она сходится к корню уравнения (2), а значит и уравнения (1). В силу сходимости итерационного процесса этот корень можно вычислить при достаточно большом n с любой заданной точностью. Однако необходимо определить при каких условиях последовательность {x_n}будет сходящейся. Получим связь между погрешностями двух соседних приближений - ε_n и ε _n+1: x_n=ξ+ε_n, x_n+1=ξ+ε _n+1. Подставим эти представления в x_n+1=φ(x_n) и разложим функцию в ряд Тейлора в окрестности корня:

ξ+ε_n+1=φ(ξ+ε_n)=φ(ξ)+ε_nφ’(ξ)+(ε_n²/2!)φ’’(η), где η  [ξ; ξ+ε_n]  [a;b].

Поскольку ξ - корень, то ξ=φ(ξ)_, то получаем:

ε_n+1=ε_n φ’(ξ)+(φ’’(η)/2)ε_n². (3)

Так как ε<1, то ε_n²<<ε_{n .} Поэтому если φ’(ξ)  0,то основной вклад в погрешность дает первое слагаемое, а слагаемым (φ’’(η)/2)ε_n² можно пренебречь, то есть

ε_{n+1 } ε_n φ’(ξ).

Это означает, что погрешность будет уменьшаться на каждом последующем шаге, если |φ’(ξ)|<1, тогда для любого n |ε_n+1|<|ε_n|. Сформулируем теорему о сходимости метода простых итераций, дающую достаточные условия сходимости.

Теорема о сходимости метода простых итераций.

Пусть ξ - корень уравнения x=φ(x), функция φ(x) определена и дифференцируема на отрезке [a,b], причем для x [a,b] все значения функции φ (x)  [a,b]. Тогда, если существует такое положительное число q<1, что при x  [a,b] выполняется неравенство |φ’(ξ)|≤q<1, то на отрезке [a,b] уравнение x=φ(x) имеет единственный корень x=ξ и процесс итераций, выраженный формулой x_n+1=φ(x_n), где n=1,2,3… , сходится к этому корню независимо от выбора начального приближения x₀  [a,b].

Таким образом, последовательность {x_n},начинающаяся с любого x₀  [a;b], сходится к корню ξ со скоростью геометрической прогрессии, причем скорость сходимости тем выше, чем меньше величина q  (1;0).

Если функция φ(х) монотонно возрастает и 0<φ’(х)<1, то все приближения лежат по одну сторону от корня - такую сходимость называют монотонной (или ступенчатой) – рис.1. Если функция φ(х) монотонно убывает и 0>φ’(х)>-1, то соседние приближения лежат по разную сторону от корня – такую сходимость называют двусторонней (или спиралевидной) – рис.2. Поскольку в этом случае корень заключен в интервале, концами которого являются соседние приближения – ξ(x_n,x_n+1), то выполнение условия |x_n+1-x_n|<ε обеспечивает выполнение условия |ξ-x _n+1|<ε.

Рис.1 Монотонное приближение Рис.2 Двустороннее приближение

к корню. к корню.

Чтобы можно было сравнивать итерационные методы по скорости сходимости, вводят следующие понятия:

Определение 1:

Сходимость последовательности {x_n} к ξ называется линейной (соответственно, итерационный процесс - линейно сходящимся), если существует такая постоянная C(0,1) и такой номер n₀, что выполняются неравенства |ξ-x_n+1|≤C|ξ-x_n| для n≥n_0.

Для введенных ранее погрешностей это означает |ε _n+1|≤C|ε_n|. В методе простой итерации в роли постоянной C выступает значение q, то есть метод сходится линейно.

Определение 2:

Последовательность приближений {x_n} сходится к ξ по меньшей мере с р-ым порядком (соответственно, итерационный процесс имеет по меньшей мере p-ый порядок), если найдутся такие константы C>0, p≥1 и n₀, что для всех n≥n₀ выполняются условия

|ξ-x_n+1|≤C|ξ-x_n |^р (или в других обозначениях |ε _n+1|≤C|ε_n|^p).

Фиксируя в определении 2 значение p=1, видим, что линейно сходящийся процесс можно назвать процессом первого порядка; значению p=2 соответствует квадратично сходящийся процесс (процесс второго порядка). К линейной сходимости применяют также термин сходимость со скоростью геометрической прогрессии.

Коснемся еще одного аспекта понятия сходимости итерационного метода. В приведенных выше рассуждениях отождествлялись сходимость итерационного процесса и сходимость итерационной последовательности, порождаемой этим процессом. При этом негласно считалось, что последовательность{x_n} уже как бы фиксирована заданием начальной точки x₀. Больший же интерес представляет сходимость множества всевозможных итерационных последовательностей, генерируемых итерационным методом при варьировании x₀ в границах некоторой области. Итерационные методы, дающие в пределе решение данной задачи при любом начальном приближении x₀, называются глобально сходящимися. Если же сходимость итерационной последовательности {x_n} к искомому элементу ξ имеет место лишь при задании x₀, из некоторой, вообще говоря, достаточно малой окрестности ξ, то соответствующий итерационный метод называется локально сходящимся.