Алгоритм нахождения корня методом Ньютона

Ввод: Функция f (х), производная f' (х), точность вычисления e корня, допуск d - малое число, связанное с реальной точностью вычисления f (х), f' (х). Промежуток [ a, b ] существования корня.

Вывод: корень с уравнения.

c:=a; если f(c)*f ''(c) < 0, то c:=b;

1. d:= c -f(c)/f '(c));

если |c - d| <e, то конец

в противном случае вычислить f (c);

если | f (c)| <d, то конец

идти к шагу 1.

Пример. Методом Ньютона найти корень уравнение x ² – sin x – 1 = 0 (точность 0,01) в интервале (1, p). Имеем f (х) = x ² – sin x – 1, a = 1, b = p» 3,1416, e = 0,01, d = 0,001. Находим

f ' (х) = 2 x – cos x, f '' (х) = 2 – sin x, c = b.

Шаг
c	3,1416	1,9238	1,5034	1,4141	1,4096
f (c)	8,8700	1,7626	0,2626	0,0121	-
f ' (c)	7,2832	4,1932	2,9396	2,6722	-

Корень уравнения: x = 1,41 ±0,01.

ВОПРОС 24 (2)

О пределение. Нормальной формой игры называется пара (ρ, F), где ρ - множество стратегий игроков (ρ₁, ρ₂), где ρ₁ - множество стратегий 1-го игрока, а ρ₂ - множество стратегий 2-го игрока; F - множество платёжных функций игроков (F₁, F₂).

О пределение. ρ₁x ρ₂ называется множеством ситуаций. Если 1-й игрок выбрал стратегию i, а 2-й - стратегию j, то говорят, что сложилась ситуация (i,j) и игра завершена. В этом случае 1-й игрок получает прибыль F₁(i,j), а 2-й - F₂(i,j).

Цель каждого из игроков - максимизация прибыли.

Виды стратегий:

1) чистая - полная определённость того, как игрок продолжит игру.

2) смешанная - указание вероятности каждой чистой стратегии (игрок выбирает одну из чистых стратегий в соответствии с заданной смешанной стратегией).

О пределение. Ситуацию игры (х, у) называют равновесием по Нэшу, если выполняются следующие неравенства:

а(х', y) <= a(x, y),

b(x, y') <= b(x, y)

для любых х⋴Х, y⋴Y (множества стратегий), где а, b - прибыли соответственно 1-го и 2-го игроков.

Критерий равновесия по Нэшу: если min_i max_j a_ij = max_j min_i a_ij, то a_ij - равновесие по Нэшу.

О пределение. Ситуация (а₁, b₁) доминирует над ситуацией (а₂, b₂), если a₁>=a₂ и b₁ >= b₂, причём хотя бы одно из этих неравенств выполняется строго.

О пределение. Парето-ситуацией называют ситуацию, над которой нет доминирующей.

Если парето-ситуация является ещё и равновесием по Нэшу, то такая ситуация является Гермейеровской.

О пределение. Антагонистические игры - игры, в которых сумма платежей равна 0. Тогда достаточно только одной компоненты и игру можно представить в матричном виде: 1-й игрок выбирает строки, 2-й - столбцы.

Пусть 1-й игрок выбрал стратегию i, 2-й - стратегию j, тогда второй платит a_ij первому. 1-й максимизирует свою прибыль, 2-й минимизирует убыток.

В матричных играх точка (i*, j*) является равновесием по Нэшу, если она максимальна в столбце и минимальна в строке.

Т еорема - основная теорема теории игр (фон Неймана). Любая игра N лиц имеет равновесие по Нэшу в смешанных стратегиях.

ВОПРОС 25 (2)