Почему не существует не итерационных/точных методов для вычисления корня из числа?

Многие методы приближенного вычисления корня, такие как метод бисекции, метод Ньютона и метод половинного деления, являются итерационными. Они используют последовательные приближения для приближенного нахождения корня.

Меня настиг вопрос, почему нету не итерационного или точного метода

Дополнительно:

И какой же точный корень из двух?

Ответы:

Если не нравится итерация - сделай через рекурсию.
Точных нет, потому что числа иррациональные

• И что с того что они иррациональны? Что мешает разработать формулу с определенной точностью (до n-знаков)?
• matsincos, Такие формулы есть. Если вам хватит точности 16% на интервале [1, 100], то возьмите гиперболическую оценку. Двоичная оценка на интервале [0.5, 2] даст точность 6.1%.

Есть же методы: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D...

Они обычно медленнее и более трудоемкие, поэтому из и не используют особо.

• Это тоже итерационный метод. На каждой итерации получается одна цифра результата.
• Rsa97, Ну, в таком случае вообще все методы итерационные. Алгоритмы-то по шагам выполняются и шаги эти - итерации.
• Wataru, Нет, итерационный метод - это метод циклических приближений, где каждое следующее значение получается из предыдущих. Если метод сходящийся, то каждое следующее значение будет ближе к точному значению, чем предыдущее.
  Поразрядное приближение выполняется циклически, использует для вычисления предыдущее значение и на каждой итерации уточняет одну цифру результата, то есть удовлетворяет всем условиям итерационного метода.
• Rsa97,
  
  

  где каждое следующее значение получается из предыдущих. Если метод сходящийся, то каждое следующее значение будет ближе к точному значению, чем предыдущее.

  Ну, тогда по вашему получается, что сортировка пузырьком - тоже итерационный метод. Следующее значение получается из предыдущего? Да. Каждый раз 2 каких-то элемента меняем, или нет. Сходится к более точному значению? Да. Точно также итерационным методом является и сложение длинных чисел столбиком, вычисление числа фибоначчи, умножение матриц, Дейкстра, FFT, любое динамическое программирование и вообще почти все на свете.

  Бред же? Потому что итерационный метод - это метод решения уравнения, основанный на поиске неподвижной точки какой-то функции. И вычисление корня по разрядам этим не является. Что там за функция-то и какая у нее неподвижная точка?

• Wataru,
  

  Что там за функция-то и какая у нее неподвижная точка?

  Функция там сложная, но это не проблема, поскольку нет какого либо единого способа задания функций, глвное, чтобы описывалось однозначное отображение одного значения в другое. Можно задать функцию формулой, можно графически, можно таблицей значений, иожно ещё каким-либо способом.
  В данном случае функция описывается алгоритмом вычисления на наборе параметров (аргумент, остаток от предыдущего шага, результат).
  А достижение стационарной точки - это только один из критериев завершения вычислений. Здесь критерием завершения может являться вычисление достаточного количества цифр результата.

  сортировка пузырьком - тоже итерационный метод

  Формально да. Функция - алгоритм поиска пар для перестановки, конечный критерий - отсутствие следующей пары.

• Формально да. Функция - алгоритм поиска пар для перестановки, конечный критерий - отсутствие следующей пары.

  Ну раз вы так считаете, то больше мне спорить не с чем. В вашей парадигме все - итеративные методы и само определение не имеет смысла.

В компьютерной науке, где-то глубоко под капотом (может, даже на уровне аппаратной реализации), все вычисления итерационные в той или иной мере.

А по поводу точности - иррациональные числа не только вычислить, а даже записать точно нельзя, например тип double - это всего 8 байт, и не получится сколько угодно после запятой. Потому в рамках типа double (или любого другого) можно говорить о "точном" значении корня из двух - о наиболее точном приближении приближении, которое поместилось в тип

• Но ведь допустим квадратный корень это обычное уравнение:
  x*x - y = 0
  В школах нас учат что решением этого уравнения является
  x = sqrt(y)

  Но тогда ведь получается рекурсия

• matsincos, Где вы тут видите рекурсию?

Всё крайне просто.
Потому что, начиная с рационального числа и проводя четыре арифметических действия, +−×: , мы будем оставаться в поле рациональных чисел. А корень в большинстве случаев иррациональный.
Мы можем получить лишь рациональное число, достаточно близкое к нашему корню.
И все «нормальные» методы вычисления корня работают так: если ещё немного повычислять, можно получить более точный корень. То есть итерационные.

Пример НЕитерационного метода предложили Ын, Уолш и Таролли, но более он известен по игре Quake III: придумать приближение логарифма, разделить на 2 и обратить это самое приближение. Но этот метод не масштабируем: если точности не хватает, придётся брать в руки какой-нибудь метод Ньютона и дотягивать точность. Ну или придумывать более точное приближение логарифма — исходное было всего лишь прочтением компьютерного дробного как целого числа. То есть придётся рубить его на мантиссу и порядок, порядок брать как есть, а мантиссу преобразовывать каким-то многочленом (если читать дробное как целое, то наш многочлен — банальная линейная функция, log₂(1+x)≈x).

А лучше порядок превратить в несмещённый, поделить надвое, вернуть опять к смещённому, и остаётся только найти приближение — многочленом или таблицей — для x∈[1,4).

Другой НЕитерационный алгоритм — банальная таблица. Каким-то раком предвычислить таблицу, а то, что в таблицу не попадает, приблизить любым доступным методом, да хоть линейной интерполяцией или многочленами Эрмита.

Тоже самое можно спросить про синус или логарифм. Все они вычисляются через числовые ряды.
Делая итерации.

Если тебе нужен аналог таблично решения - то ты можешь расчитать функцию заранее
в некоторых точках и пользуясь гладкостью просто вычислять интерполяцию.

Вот тебе и будет почти точный метод.