Что приближает следующий алгоритм? (Предположим, что m> 1, ϵ> 0)

Question

x = m;
y = 1;
While (x-y > ϵ)
{
    x = (x+y)/2;
    y = m/x;
}
print(x);

Ответ: \ sqrt {m}

Я не знаю, как прийти к такому выводу, потому что я не знаю значение ϵ, я пробовал, но в результате получил кучу уравнений что для меня не имеет смысла.

Пожалуйста, помогите мне понять, как понимать и разбивать этот тип вопросов. Спасибо

Answer 1

Обратите внимание, что:

• l oop будет продолжаться до тех пор, пока x и y не окажутся в пределах ϵ друг от друга;
• y = m / x ⇒ y * x = m на каждой итерации.

Когда условие остановки выполнено, мы знаем, что x * (x - ϵ) = x ² - ϵx = m. Следовательно, при ϵ → 0 это означает, что x ² → m, поэтому x (и y) должны сходиться к sqrt (m). ϵ - это допуск, который вы указываете для этого схождения.

Answer 2

Я бы сказал, может быть, выберите язык, реализуйте свой алгоритм, затем распечатайте все, вы увидите, как алгоритм выполняет задачу шаг за шагом:

Например, в Python ваш алгоритм, вероятно, выглядят так:

ϵ = 10
m = 30
x = m
y = 1

while x - y > ϵ:
    x = (x + y) // 2
    y = m // x

print(x)

Если бы мы распечатали переменные алгоритма, где бы вы ни хотели и шаг за шагом, вы бы наблюдали, как работает алгоритм:

ϵ = 4
m = 90
x = m
y = 1

step = 0
while x - y > ϵ:
    step += 1
    print(f'-----------------step {step}----------------')
    print(f'x before first operation is {x}')
    print(f'y before first operation is {y}')
    print(f'ϵ before first operation is {ϵ}')
    print(f'x - y before first operation is {x - y}')
    print(f'm before first operation is {m}')
    x = (x + y) // 2

    print(f'x after first operation is {x}')
    print(f'y after first operation is {y}')
    print(f'ϵ after first operation is {ϵ}')
    print(f'x - y after first operation is {x - y}')
    print(f'm after first operation is {m}')

    y = m // x

    print(f'x after second operation is {x}')
    print(f'y after second operation is {y}')
    print(f'ϵ after second operation is {ϵ}')
    print(f'x - y after second operation is {x - y}')
    print(f'm after second operation is {m}')

print(x)

Вывод

-----------------step 1----------------
x before first operation is 90
y before first operation is 1
ϵ before first operation is 4
x - y before first operation is 89
m before first operation is 90
x after first operation is 45
y after first operation is 1
ϵ after first operation is 4
x - y after first operation is 44
m after first operation is 90
x after second operation is 45
y after second operation is 2
ϵ after second operation is 4
x - y after second operation is 43
m after second operation is 90
-----------------step 2----------------
x before first operation is 45
y before first operation is 2
ϵ before first operation is 4
x - y before first operation is 43
m before first operation is 90
x after first operation is 23
y after first operation is 2
ϵ after first operation is 4
x - y after first operation is 21
m after first operation is 90
x after second operation is 23
y after second operation is 3
ϵ after second operation is 4
x - y after second operation is 20
m after second operation is 90
-----------------step 3----------------
x before first operation is 23
y before first operation is 3
ϵ before first operation is 4
x - y before first operation is 20
m before first operation is 90
x after first operation is 13
y after first operation is 3
ϵ after first operation is 4
x - y after first operation is 10
m after first operation is 90
x after second operation is 13
y after second operation is 6
ϵ after second operation is 4
x - y after second operation is 7
m after second operation is 90
-----------------step 4----------------
x before first operation is 13
y before first operation is 6
ϵ before first operation is 4
x - y before first operation is 7
m before first operation is 90
x after first operation is 9
y after first operation is 6
ϵ after first operation is 4
x - y after first operation is 3
m after first operation is 90
x after second operation is 9
y after second operation is 10
ϵ after second operation is 4
x - y after second operation is -1
m after second operation is 90
9

Этот ответ также объясняет это просто.