Подделки правил

В математике regula falsi , метод ложного положения или метод ложного положения — очень старый метод решения уравнения с одним неизвестным; этот метод в модифицированной форме используется до сих пор. Проще говоря, этот метод представляет собой метод проб и ошибок , заключающийся в использовании тестовых («ложных») значений переменной и последующей корректировке тестового значения в соответствии с результатом. Иногда это также называют «угадай и проверь». Версии метода появились еще до появления алгебры и использования уравнений .

В качестве примера рассмотрим задачу 26 в папирусе Ринда , которая требует решения (записанного в современных обозначениях) уравнения $x + .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ Икс / 4 ⁠ знак равно 15$ . Это решается ложной позицией. ^[1] Сначала предположим, что $x = 4$ , чтобы получить слева 4 + ⁠ 4 / 4 ⁠ знак равно 5 . Это предположение является хорошим выбором, поскольку оно дает целочисленное значение. Однако число 4 не является решением исходного уравнения, поскольку оно дает значение, в три раза меньшее. Чтобы компенсировать это, умножьте $x$ (сейчас установлено значение 4) на 3 и подставьте снова, чтобы получить 12 + ⁠ 12 / 4 ⁠ = 15 , проверяя, что решение — $x = 12$ .

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

Два исторических типа

Исторически можно выделить два основных типа метода ложной позиции: простую ложную позицию и двойную ложную позицию .

Простая ложная позиция направлена на решение проблем, связанных с прямой пропорциональностью. Такие задачи можно записать алгебраически в виде: определить $x$ такой, что

ax=b,

если $a$ и $b$ известны. Метод начинается с использования тестового входного значения $x'$ и нахождения соответствующего выходного значения $b'$ путем умножения: $ax' = b'$ . Правильный ответ затем находится путем пропорциональной корректировки, $x = ⁠ б / б' ⁠ Икс'$ .

Двойная ложная позиция направлена на решение более сложных задач, которые можно алгебраически записать в виде: определить $x$ такой, что

f(x)=ax+c=0,

если известно, что

f(x_{1})=b_{1},\qquad f(x_{2})=b_{2}.

Двойное ложное положение математически эквивалентно линейной интерполяции . Используя пару тестовых входных данных и соответствующую пару выходных данных, результат этого алгоритма определяется формулой: ^[2]

x={\frac {b_{1}x_{2}-b_{2}x_{1}}{b_{1}-b_{2}}},

будет запоминаться и выполняться наизусть. Действительно, правило, данное Робертом Рекордом в его «Основе искусств» (ок. 1542 г.): ^[2]

Гессе, как и следовало ожидать, руководит этой работой.
Случайно вы можете продолжить.
И сначала задаюсь вопросом:
Хотя никакой правды в этом нет.
Такая ложь — такое хорошее основание,
Эта истина вскоре будет найдена.
От многих бате до многих мо,
От to smalle также возьмите to lesse.
Снова слишком много иои, чтобы мало,
Чтобы мало добавить ко многим равнинам.
В перекрестках умножай противоположный вид,
Вся правда за ложью, чтобы найти.

Для аффинной линейной функции

f(x)=ax+c,

двойное ложное положение обеспечивает точное решение, тогда как для нелинейной функции $f$ оно обеспечивает приближение , которое можно последовательно улучшать путем итерации .

История

Простая техника ложной позиции встречается в клинописных табличках древней вавилонской математики и в папирусах древнеегипетской математики . ^[3]^[1]

Двойная ложная позиция возникла в поздней античности как чисто арифметический алгоритм. В древнем китайском математическом тексте « Девять глав математического искусства» (九章算術) ^[4] датированный периодом с 200 г. до н. э. по 100 г. н. э., большая часть главы 7 была посвящена алгоритму. Там процедура была обоснована конкретными арифметическими аргументами, а затем творчески применена к широкому кругу задач истории, включая задачу, связанную с тем, что мы бы назвали секущими линиями на коническом сечении . Более типичным примером является задача «совместной покупки», включающая условие «избытка и дефицита»: ^[5]

Теперь предмет приобретается совместно; каждый вносит по 8 [монет], избыток — 3; каждый вносит 7, дефицит 4. Скажите: Количество человек, цена предмета, сколько у каждого? Ответ: 7 человек, цена товара 53. ^[6]

Между 9 и 10 веками египетский математик Абу Камиль написал ныне утерянный трактат об использовании двойной ложной позиции, известный как « Книга двух ошибок» ( Китаб аль-Хатаайн ). Самое старое из сохранившихся сочинений о двойной ложной позиции на Ближнем Востоке принадлежит Кусте ибн Луке (10 век), арабскому математику из Баальбека , Ливан . Он обосновал эту технику формальным геометрическим доказательством в евклидовом стиле . В традиции средневековой мусульманской математики двойная ложная позиция была известна как хисаб аль-хатаайн («расчет по двум ошибкам»). Он использовался на протяжении веков для решения практических проблем, таких как коммерческие и юридические вопросы (раздел имущества в соответствии с правилами наследования Корана ), а также чисто развлекательные проблемы. Алгоритм часто запоминался с помощью мнемоники , такой как стих, приписываемый Ибн аль-Ясамину , и диаграммы весов, объясненные аль-Хассаром и Ибн аль-Банной , все трое были математиками марокканского происхождения. ^[7]

Леонардо Пизанский ( Фибоначчи ) посвятил главу 13 своей книги Liber Abaci (1202 г. н. э.) объяснению и демонстрации использования двойной ложной позиции, назвав метод regulis elchatayn в честь метода аль-хатаайн , который он узнал из арабских источников. ^[7] В 1494 году Пачоли использовал термин el cataym в своей книге «Сумма арифметики» , вероятно, взяв этот термин у Фибоначчи. Другие европейские писатели следовали Пачоли и иногда переводили его на латынь или местный язык. Например, Тарталья переводит латинизированную версию термина Пачоли на просторечие «ложные позиции» в 1556 году. ^[8] Термин Пачоли почти исчез в европейских работах XVI века, и эта техника носила различные названия, такие как «Правило ложной позиции», «Правило позиции» и «Правило ложной позиции». Регула Фалси появляется как латинизированная версия Правила Ложи еще в 1690 году. ^[2]

Несколько европейских авторов XVI века почувствовали необходимость извиниться за название метода в науке, стремящейся найти истину. Например, в 1568 году Хамфри Бейкер говорит: ^[2]

Правило лжи названо так не потому, что оно учит кого-либо обману или лжи, а потому, что с помощью притворных чисел, взятых во всех случаях, оно учит находить истинное число, которое подвергается критике, и это из всех вульгарных правил, которые применяются на практике. ) это у ^и самое превосходство.

Численный анализ

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

Многие уравнения, в том числе большинство наиболее сложных, могут быть решены только путем итерационной численной аппроксимации. Это состоит из проб и ошибок, в ходе которых проверяются различные значения неизвестной величины. Методом проб и ошибок можно руководствоваться путем расчета на каждом этапе процедуры новой оценки решения. Есть много способов получить расчетную оценку, и Regula Falsi предлагает один из них.

Учитывая уравнение, переместите все его члены в одну сторону так, чтобы оно имело вид $f (x) = 0$ , где $f$ — некоторая функция неизвестной переменной $x$ . Значение $c,$ которое удовлетворяет этому уравнению, то есть $f (c) = 0$ , называется корнем или нулем функции $f$ и является решением исходного уравнения. Если $f$ — непрерывная функция существуют две точки $и ($ b0 $такие f$ , что $(a0) имеет и$ f $a0 b0) и имеют$ противоположные знаки, то по теореме о промежуточном значении функция $f$ корень в интервал $(а 0, б 0)$ .

Существует множество алгоритмов поиска корня , которые можно использовать для получения приближений к такому корню. Одним из наиболее распространенных является метод Ньютона функции , но при определенных обстоятельствах он может не найти корень и может оказаться дорогостоящим в вычислительном отношении, поскольку требует вычисления производной . Требуются и другие методы, и одним общим классом методов являются методы двухточечной скобки . создании последовательности сокращающихся интервалов $[ak (, bk Эти]$ на $k$ -м шаге, таких, $ak, методы основаны на bk) что содержит$ корень $f$ .

Методы двухточечного брекетинга

Эти методы начинаются с двух $значений x$ , первоначально найденных методом проб и ошибок, при которых $f (x)$ имеет противоположные знаки. В предположении непрерывности корень $f$ гарантированно находится между этими двумя значениями, то есть эти значения заключают корень в квадратные скобки. Затем выбирается точка строго между этими двумя значениями и используется для создания меньшего интервала, который по-прежнему заключает в скобки корень. Если $c$ выбрана точка, то меньший интервал идет от $c$ до конечной точки, где $f (x)$ имеет знак, противоположный знаку $f (c)$ . В маловероятном случае, когда $f (c) = 0$ , корень найден и алгоритм останавливается. В противном случае процедура повторяется столько раз, сколько необходимо для получения аппроксимации корня с любой желаемой точностью.

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

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

Самый простой вариант, называемый методом деления пополам , вычисляет оценку решения как среднюю точку интервала брекетинга. То есть, если на шаге $текущий$ интервал брекетинга равен $[ak :, bk, то новая]$ оценка решения $ck k$ получается по формуле

c_{k}={\frac {a_{k}+b_{k}}{2}}.

Это гарантирует, что $c k$ находится между $a k$ и $b k$ , тем самым гарантируя сходимость к решению.

Поскольку длина интервала брекетинга уменьшается вдвое на каждом шаге, ошибка метода деления пополам уменьшается в среднем вдвое с каждой итерацией. Следовательно, каждые 3 итерации метод выигрывает примерно в 2 раза. ³, т.е. примерно до десятичной точки по точности.

Метод regula falsi (ложного положения).

Скорость сходимости метода деления пополам можно улучшить, используя другую оценку решения.

Метод regula falsi вычисляет новую оценку решения как $x$ отрезка, с точку пересечения соединяющего конечные точки функции на текущем интервале брекетинга. По сути, корень аппроксимируется путем замены фактической функции сегментом линии на интервале брекетинга, а затем с использованием классической формулы двойной ложной позиции на этом сегменте линии. ^[9]

Точнее, предположим, что на $й$ итерации интервал брекетинга равен $(ak k, bk -)$ . Постройте линию через точки $(a k, f (a k))$ и $(b k, f (b k))$ , как показано на рисунке. Эта линия является секущей или хордой графика функции $f$ . В форме точечного наклона его уравнение имеет вид

y-f(b_{k})={\frac {f(b_{k})-f(a_{k})}{b_{k}-a_{k}}}(x-b_{k}).

Теперь выберите $c k$ в качестве $точки пересечения с x$ этой линии, то есть значение $x,$ для которого $y = 0$ , и подставьте эти значения, чтобы получить

f(b_{k})+{\frac {f(b_{k})-f(a_{k})}{b_{k}-a_{k}}}(c_{k}-b_{k})=0.

Решение этого уравнения для c _k дает:

c_{k}=b_{k}-f(b_{k}){\frac {b_{k}-a_{k}}{f(b_{k})-f(a_{k})}}={\frac {a_{k}f(b_{k})-b_{k}f(a_{k})}{f(b_{k})-f(a_{k})}}.

Эта последняя симметричная форма имеет вычислительное преимущество:

По мере приближения к решению $a k$ и $b k$ будут очень близки друг к другу и почти всегда будут иметь один и тот же знак. Такое вычитание может привести к потере значащих цифр. Поскольку $f (b k)$ и $f (a k)$ всегда имеют противоположный знак, «вычитание» в числителе улучшенной формулы фактически является сложением (как и вычитание в знаменателе).

На итерации номер $k$ число $c k$ вычисляется, как указано выше, а затем, если $f (a k)$ и $f (c k)$ имеют одинаковый знак, устанавливают $a k + 1 = c k$ и $b k + 1 = b k$ , в противном случае установите $a k + 1 = a k$ и $b k + 1 = c k$ . Этот процесс повторяется до тех пор, пока корень не будет достаточно хорошо аппроксимирован.

Приведенная выше формула также используется в методе секущего, но метод секущего всегда сохраняет две последние вычисленные точки, поэтому, хотя он и немного быстрее, он не сохраняет брекетинг и может не сходиться.

Тот факт, что regula falsi всегда сходится и имеет версии, которые хорошо предотвращают замедление, делает его хорошим выбором, когда необходима скорость. Однако его скорость сходимости может упасть ниже скорости сходимости метода пополам.

Анализ

Поскольку начальные конечные точки $a 0$ и $b 0$ выбраны так, что $f (a 0)$ и $f (b 0)$ имеют противоположные знаки, на каждом шаге одна из конечных точек будет приближаться к корню $f$ . Если вторая производная $f$ имеет постоянный знак (поэтому нет точки перегиба ) на интервале, то одна конечная точка (та, где $f$ тоже имеет тот же знак) останется фиксированной для всех последующих итераций, пока сходящаяся конечная точка обновляется. Как результат, в отличие от метода деления пополам , ширина скобки не имеет тенденции к увеличению. ноль (если только ноль не находится в точке перегиба, вокруг которой $знак (f) = -sign(f ")$ ). Как следствие, линейное приближение к $f (x)$ , которое используется для выбора ложного положения, не улучшается настолько быстро, насколько это возможно.

Одним из примеров этого явления является функция

f(x)=2x^{3}-4x^{2}+3x

на начальной скобке [−1,1]. Левый конец -1 никогда не заменяется (сначала он не меняется, а после первых трех итераций $f "$ отрицательна на интервале) и, следовательно, ширина скобки никогда не опускается ниже 1. Следовательно, правая конечная точка приближается к 0 в точке линейная скорость (количество точных цифр растет линейно, со скоростью сходимости 2/3). ^{[ нужна ссылка ]}

Для разрывных функций можно ожидать, что этот метод найдет только точку, в которой функция меняет знак (например, при $x = 0$ для $1/ x$ или знаковой функции ). Помимо смены знака, метод также может сходиться к точке, где предел функции равен нулю, даже если функция не определена (или имеет другое значение) в этой точке (например, при $x = 0$ для функция, заданная $f (x) = abs (x) - x 2$ когда $x \neq 0$ и $f (0) = 5$ , начиная с интервала [-0,5, 3,0]). Математически возможно, что метод с разрывными функциями не сможет достичь нулевого предела или смены знака, но на практике это не проблема, поскольку для того, чтобы обе конечные точки застряли, сходящиеся к разрывам, потребовалась бы бесконечная последовательность совпадений. знак не меняется, например при $x = \pm1$ в

f(x)={\frac {1}{(x-1)^{2}}}+{\frac {1}{(x+1)^{2}}}.

Метод деления пополам позволяет избежать этой гипотетической проблемы сходимости.

Улучшения в regula falsi

Хотя regula falsi всегда сходится, обычно значительно быстрее, чем пополам, существуют ситуации, которые могут замедлить ее сближение – иногда до запретительной степени. Эта проблема не уникальна для regula falsi : за исключением деления пополам, все методы численного решения уравнений при некоторых условиях могут иметь проблему медленной сходимости или отсутствия сходимости. Иногда метод Ньютона и метод секущих расходятся, а не сходятся, и часто это происходит при тех же условиях, которые замедляют сходимость regula falsi .

Но хотя regula falsi является одним из лучших методов, и даже в своей первоначальной неулучшенной версии часто будет лучшим выбором; например, когда Ньютон не используется, потому что для вычисления производной требуется слишком много времени, или когда Ньютон и последовательные замены не смогли сойтись.

Режим отказа Regula falsi легко обнаружить: одна и та же конечная точка сохраняется дважды подряд. Проблему легко решить, выбрав вместо этого модифицированную ложную позицию, выбранную во избежание замедления из-за этих относительно необычных неблагоприятных ситуаций. ряд таких улучшений в Regula Falsi Был предложен ; два из них, алгоритм Иллинойса и алгоритм Андерсона-Бьорка, описаны ниже.

Алгоритм Иллинойса

Алгоритм Иллинойса уменьшает вдвое $значение y$ сохраненной конечной точки при следующем вычислении оценки, когда новое $значение y$ (то есть $f (c k$ )) имеет тот же знак, что и предыдущее ( $f (c k - 1$ ) ), что означает, что конечная точка предыдущего шага будет сохранена. Следовательно:

c_{k}={\frac {{\frac {1}{2}}f(b_{k})a_{k}-f(a_{k})b_{k}}{{\frac {1}{2}}f(b_{k})-f(a_{k})}}

или

c_{k}={\frac {f(b_{k})a_{k}-{\frac {1}{2}}f(a_{k})b_{k}}{f(b_{k})-{\frac {1}{2}}f(a_{k})}},

уменьшение веса одного из значений конечной точки, чтобы заставить следующий $c k$ произойти на этой стороне функции. ^[10] Фактор Используемое выше ⁠ 1/2 выглядит произвольным, но оно гарантирует суперлинейную сходимость ⁠ ( асимптотически алгоритм выполнит два обычных шага после любого измененного шага и имеет порядок сходимости 1,442). Есть и другие способы выбора масштабирования, которые дают еще лучшие скорости суперлинейной сходимости. ^[11]

Вышеупомянутую корректировку Regula Falsi называют алгоритмом Иллинойса . некоторые ученые ^[10]^[12] Форд (1995) обобщает и анализирует этот и другие подобные суперлинейные варианты метода ложного положения. ^[11]

Алгоритм Андерсона – Бьорка

Предположим, что на $,$ bk $] и k-й итерации интервалом брекетинга является [ak что функциональное что значение$ вычисленной оценки $ck и$ имеет тот же знак, $f (bk новой)$ . В этом случае новый интервал брекетинга $[a k + 1, b k + 1] = [a k, c k]$ и левая конечная точка были сохранены. (Пока это то же самое, что и обычный Регула Фалси и алгоритм Иллинойса.)

Но, в то время как алгоритм Иллинойса умножал бы $f (a k)$ на ⁠ 1/2 имеет одно из ⁠ алгоритм Андерсона–Бьорка умножает его на $m$ , где $m$ двух следующих значений: ^[13]

${\begin{aligned}m'&=1-{\frac {f(c_{k})}{f(b_{k})}},\\m&={\begin{cases}m'&{\text{if }}m'>0,\\{\frac {1}{2}}&{\text{otherwise.}}\end{cases}}\end{aligned}}$

Для простых корней на практике очень хорошо работает метод Андерсона-Бьорка. ^[14]

метод ИТП

Данный $\kappa _{1}\in (0,\infty ),\kappa _{2}\in \left[1,1+\phi \right)$ , $n_{1/2}\equiv \lceil (b_{0}-a_{0})/2\epsilon \rceil$ и $n_{0}\in [0,\infty )$ где $\phi$ это золотое сечение ${\tfrac {1}{2}}(1+{\sqrt {5}})$ , в каждой итерации $j=0,1,2...$ метод ITP вычисляет точку $x_{\text{ITP}}$ следующие три шага:

[Шаг интерполяции] Вычисление биссектрисы и ложных точек: $x_{1/2}\equiv {\frac {a+b}{2}}$ и $x_{f}\equiv {\frac {bf(a)-af(b)}{f(a)-f(b)}}$ ;
[Шаг усечения] Возмущаем оценщик по направлению к центру: $x_{t}\equiv x_{f}+\sigma \delta$ где $\sigma \equiv {\text{sign}}(x_{1/2}-x_{f})$ и $\delta \equiv \min\{\kappa _{1}|b-a|^{\kappa _{2}},|x_{1/2}-x_{f}|\}$ ;
[Шаг проецирования] Спроецируйте оценщик на минмаксный интервал: $x_{\text{ITP}}\equiv x_{1/2}-\sigma \rho _{k}$ где $\rho _{k}\equiv \min \left\{\epsilon 2^{n_{1/2}+n_{0}-j}-{\frac {b-a}{2}},|x_{t}-x_{1/2}|\right\}$ .

Значение функции $f(x_{\text{ITP}})$ в этой точке запрашивается, а затем интервал сокращается до корня, сохраняя подинтервал со значениями функции противоположного знака на каждом конце. Эта трехэтапная процедура гарантирует, что оценка будет обладать минмаксными свойствами метода деления пополам, а также сверхлинейной сходимостью метода секущего. Кроме того, наблюдается превосходство методов, основанных на делении пополам и интерполяции, при работе с гладкими и негладкими функциями. ^[15]

Практические соображения

При решении одного или нескольких уравнений с помощью компьютера метод деления пополам является подходящим выбором. Хотя деление пополам не так быстро, как другие методы (когда они работают лучше всего и не вызывают проблем), деление пополам, тем не менее, гарантированно сходится с полезной скоростью, примерно вдвое уменьшая ошибку с каждой итерацией, получая примерно десятичный результат. место точности через каждые 3 итерации.

Для ручного расчета с помощью калькулятора обычно хочется использовать более быстрые методы, и они обычно, но не всегда, сходятся быстрее, чем деление пополам. Но компьютер, даже используя деление пополам, решит уравнение с желаемой точностью настолько быстро, что нет необходимости пытаться сэкономить время, используя менее надежный метод — а каждый метод менее надежен, чем деление пополам.

Исключением может быть случай, когда компьютерной программе во время работы приходится решать уравнения очень много раз. Тогда время, сэкономленное более быстрыми методами, может быть значительным.

Затем программа может начаться с метода Ньютона и, если метод Ньютона не сходится, переключиться на regula falsi , возможно, в одну из его улучшенных версий, таких как версии Иллинойса или Андерсона-Бьорка. Или, если даже это не сходится так хорошо, как деление пополам, переключитесь на деление пополам, которое всегда сходится с полезной, если не впечатляющей, скоростью.

Когда изменение $y$ стало очень малым, а $x$ также меняется очень мало, то метод Ньютона, скорее всего, не столкнется с проблемами и сойдётся. Итак, при этих благоприятных условиях можно было бы переключиться на метод Ньютона, если бы хотелось, чтобы ошибка была очень маленькой и хотелось бы очень быстрой сходимости.

Пример: рост камыша.

В главе 7 «Девяти глав » проблему поиска корня можно перевести на современный язык следующим образом:

Проблема избытка и дефицита № 11:

единицы . В первый день камыш вырос на 3 В конце каждого дня наблюдается рост растения на ⁠ 1/2 ⁠ предыдущего роста дня.

В первый день клубная лихорадка выросла на 1 единицу. В конце каждого дня растение выросло в 2 раза больше, чем прирост предыдущего дня.

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

Отвечать: $(2+{\frac {6}{13}})$ дни; высота $(4+{\frac {8}{10}}+{\frac {6}{130}})$ единицы.
Объяснение:

Предположим, это день 2. Булава короче камыша на 1,5 единицы.

Предположим, день третий. Булава выше камыша на 1,75 единицы. ∎

Чтобы понять это, мы смоделируем высоту растений в день $n$ ( $n$ = 1, 2, 3...) по геометрическому ряду .

B(n)=\sum _{i=1}^{n}3\cdot {\frac {1}{2^{i-1}}}\quad

камыш

C(n)=\sum _{i=1}^{n}1\cdot 2^{i-1}\quad

Клуб-раш

Для удобства обозначений пусть $\ k=i-1~.$ Перепишите ряд высот растений. $\ B(n),\ C(n)\$ через $k$ и вызвать формулу суммы .

\ B(n)=\sum _{k=0}^{n-1}3\cdot {\frac {1}{2^{k}}}=3\left({\frac {1-({\tfrac {1}{2}})^{n-1+1}}{1-{\tfrac {1}{2}}}}\right)=6\left(1-{\frac {1}{2^{n}}}\right)

\ C(n)=\sum _{k=0}^{n-1}2^{k}={\frac {~~1-2^{n}}{\ 1-2\ }}=2^{n}-1\

Теперь используйте regula falsi , чтобы найти корень $\ (C(n)-B(n))\$

\ F(n):=C(n)-B(n)={\frac {6}{2^{n}}}+2^{n}-7\

Набор $\ x_{1}=2\$ и вычислить $\ F(x_{1})=F(2)\$ что равно $-1,5$ («дефицит»).
Набор $\ x_{2}=3\$ и вычислить $\ F(x_{2})=F(3)\$ что равно $1,75$ («превышение»).

Предполагаемый корень (1-я итерация):

\ {\hat {x}}~=~{\frac {~x_{1}F(x_{2})-x_{2}F(x_{1})~}{F(x_{2})-F(x_{1})}}~=~{\frac {~2\times 1.75+3\times 1.5~}{1.75+1.5}}~\approx ~2.4615\

Пример кода

Этот пример программы, написанный на языке программирования C , является примером алгоритма Иллинойса. Чтобы найти положительное число $x$ , где $cos(x) = x 3$ , уравнение преобразуется в форму поиска корня $f (x) = cos(x) -- x 3 = 0$ .

#include <stdio.h>
#include <math.h>

double f(double x) {
   return cos(x) - x*x*x;
}
/* a,b: endpoints of an interval where we search
   e: half of upper bound for relative error
   m: maximal number of iteration
*/
double FalsiMethod(double (*f)(double), double a, double b, double e, int m) {
   double c, fc;
   int n, side = 0;
   /* starting values at endpoints of interval */
   double fa = f(a);
   double fb = f(b);

   for (n = 0; n < m; n++) {
      c = (fa * b - fb * a) / (fa - fb);
      if (fabs(b - a) < e * fabs(b + a))
         break;
      fc = f(c);

      if (fc * fb > 0) {
         /* fc and fb have same sign, copy c to b */
         b = c; fb = fc;
         if (side == -1)
            fa /= 2;
         side = -1;
      } else if (fa * fc > 0) {
         /* fc and fa have same sign, copy c to a */
         a = c; fa = fc;
         if (side == +1)
            fb /= 2;
         side = +1;
      } else {
         /* fc * f_ very small (looks like zero) */
         break;
      }
   }
   return c;
}

int main(void) {
   printf("%0.15f\n", FalsiMethod(&f, 0, 1, 5E-15, 100));
   return 0;
}

После запуска этого кода окончательный ответ будет примерно 0,865474033101614.

См. также

Метод ITP , вариант с гарантированным минимумом и суперлинейной сходимостью.
Метод Риддерса , еще один метод поиска корня, основанный на методе ложного положения.
метод Брента

Ссылки

^ Перейти обратно: ^а ^б Кац, Виктор Дж. (1998), История математики (2-е изд.), Аддисон Уэсли Лонгман, стр. 15 , ISBN 978-0-321-01618-8
^ Перейти обратно: ^а ^б ^с ^д Смит, Д.Э. (1958) [1925], История математики , том. II, Дувр, стр. 437–441, ISBN. 978-0-486-20430-7
^ Шабер, Жан-Люк, изд. (2012) [1999]. «3. Методы ложной позиции» . История алгоритмов: от камешка до микрочипа . Спрингер. стр. 86–91. ISBN 978-3-642-18192-4 .
^ Нидхэм, Джозеф (1959). Математика и науки о небе и земле . Наука и цивилизация в Китае. Том. 3. Издательство Кембриджского университета. стр. 147–. ISBN 978-0-521-05801-8 .
^ «Девять глав» . www-groups.dcs.st-and.ac.uk . Проверено 16 февраля 2019 г.
^ Шен, Каншен; Кроссли, Джон Н.; Лунь, Энтони Ва-Чунг (1999). Девять глав математического искусства: спутник и комментарий . Издательство Оксфордского университета. п. 358. ИСБН 978-7-03-006101-0 .
^ Перейти обратно: ^а ^б Шварц, РК (2004). Проблемы происхождения и развития Хисаб аль-Хатаайн (расчет по двойной ложной позиции) . Восьмое североафриканское совещание по истории арабской математики. Радес, Тунис. Доступно онлайн по адресу: http://facstaff.uindy.edu/~oaks/Biblio/COMHISMA8paper.doc и «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 16 мая 2014 г. Проверено 8 июня 2012 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )
^ Общий трактат , т. I, Венеция, 1556, с. фол. 238, v, Правило Хелкатайма (арабское слово), которое на нашем языке означает ложные положения.
^ Конте, SD; Бур, Карл де (1965). Элементарный численный анализ: алгоритмический подход (2-е изд.). МакГроу-Хилл. п. 40. OCLC 1088854304 .
^ Перейти обратно: ^а ^б Далквист, Гермунд ; Бьорк, Оке (2003) [1974]. Численные методы . Дувр. стр. 231–232. ISBN 978-0486428079 .
^ Перейти обратно: ^а ^б Форд, Дж. А. (1995), Улучшенные алгоритмы типа Иллинойса для численного решения нелинейных уравнений , Технический отчет, University of Essex Press, CiteSeerX 10.1.1.53.8676 , CSM-257
^ Доуэлл, М.; Джарратт, П. (1971). «Модифицированный метод regula falsi для вычисления корня уравнения». КУСОЧЕК . 11 (2): 168–174. дои : 10.1007/BF01934364 . S2CID 50473598 .
^ Кинг, Ричард Ф. (октябрь 1983 г.). «Андерсон-Бьорк для линейных последовательностей». Математика вычислений . 41 (164): 591–596. дои : 10.2307/2007695 . JSTOR 2007695 .
^ Галдино, Серджио (2011). «Семейство методов поиска корней regula falsi» . Материалы Всемирного конгресса по технике и технологиям 2011 года . 1 . Проверено 9 сентября 2016 г.
^ Оливейра, IFD; Такахаши, RHC (06 декабря 2020 г.). «Улучшение средней производительности метода бисекции с сохранением минмаксной оптимальности» . Транзакции ACM в математическом программном обеспечении . 47 (1): 5:1–5:24. дои : 10.1145/3423597 . ISSN 0098-3500 . S2CID 230586635 .

Дальнейшее чтение

Берден, Ричард Л.; Фейрес, Дж. Дуглас (2000). Численный анализ (7-е изд.). Брукс/Коул. ISBN 0-534-38216-9 .
Сиглер, LE (2002). «Liber Abaci» Фибоначчи, «Книга вычислений» Леонардо Пизано . Спрингер Верлаг. ISBN 0-387-40737-5 .
Робертс, AM (2020). «Математическая филология в трактате о двойной ложной позиции в арабской рукописи в Колумбийском университете» . Филологические встречи . 5 (3–4): 3–4. дои : 10.1163/24519197-BJA10007 . S2CID 229538951 . (О ранее неопубликованном трактате о двойной ложной позиции в средневековой арабской рукописи.)

[Katz-1] Перейти обратно: ^а ^б Кац, Виктор Дж. (1998), История математики (2-е изд.), Аддисон Уэсли Лонгман, стр. 15 , ISBN 978-0-321-01618-8

[Smith-2] Перейти обратно: ^а ^б ^с ^д Смит, Д.Э. (1958) [1925], История математики , том. II, Дувр, стр. 437–441, ISBN. 978-0-486-20430-7

[3] Шабер, Жан-Люк, изд. (2012) [1999]. «3. Методы ложной позиции» . История алгоритмов: от камешка до микрочипа . Спрингер. стр. 86–91. ISBN 978-3-642-18192-4 .

[Needham1959-4] Нидхэм, Джозеф (1959). Математика и науки о небе и земле . Наука и цивилизация в Китае. Том. 3. Издательство Кембриджского университета. стр. 147–. ISBN 978-0-521-05801-8 .

[5] «Девять глав» . www-groups.dcs.st-and.ac.uk . Проверено 16 февраля 2019 г.

[6] Шен, Каншен; Кроссли, Джон Н.; Лунь, Энтони Ва-Чунг (1999). Девять глав математического искусства: спутник и комментарий . Издательство Оксфордского университета. п. 358. ИСБН 978-7-03-006101-0 .

[Schwartz-7] Перейти обратно: ^а ^б Шварц, РК (2004). Проблемы происхождения и развития Хисаб аль-Хатаайн (расчет по двойной ложной позиции) . Восьмое североафриканское совещание по истории арабской математики. Радес, Тунис. Доступно онлайн по адресу: http://facstaff.uindy.edu/~oaks/Biblio/COMHISMA8paper.doc и «Архивная копия» (PDF) . Архивировано из оригинала (PDF) 16 мая 2014 г. Проверено 8 июня 2012 г. {{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )

[8] Общий трактат , т. I, Венеция, 1556, с. фол. 238, v, Правило Хелкатайма (арабское слово), которое на нашем языке означает ложные положения.

[9] Конте, SD; Бур, Карл де (1965). Элементарный численный анализ: алгоритмический подход (2-е изд.). МакГроу-Хилл. п. 40. OCLC 1088854304 .

[Dahlquist-10] Перейти обратно: ^а ^б Далквист, Гермунд ; Бьорк, Оке (2003) [1974]. Численные методы . Дувр. стр. 231–232. ISBN 978-0486428079 .

[Ford-11] Перейти обратно: ^а ^б Форд, Дж. А. (1995), Улучшенные алгоритмы типа Иллинойса для численного решения нелинейных уравнений , Технический отчет, University of Essex Press, CiteSeerX 10.1.1.53.8676 , CSM-257

[12] Доуэлл, М.; Джарратт, П. (1971). «Модифицированный метод regula falsi для вычисления корня уравнения». КУСОЧЕК . 11 (2): 168–174. дои : 10.1007/BF01934364 . S2CID 50473598 .

[13] Кинг, Ричард Ф. (октябрь 1983 г.). «Андерсон-Бьорк для линейных последовательностей». Математика вычислений . 41 (164): 591–596. дои : 10.2307/2007695 . JSTOR 2007695 .

[14] Галдино, Серджио (2011). «Семейство методов поиска корней regula falsi» . Материалы Всемирного конгресса по технике и технологиям 2011 года . 1 . Проверено 9 сентября 2016 г.

[15] Оливейра, IFD; Такахаши, RHC (06 декабря 2020 г.). «Улучшение средней производительности метода бисекции с сохранением минмаксной оптимальности» . Транзакции ACM в математическом программном обеспечении . 47 (1): 5:1–5:24. дои : 10.1145/3423597 . ISSN 0098-3500 . S2CID 230586635 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

v т и Алгоритмы поиска корня
Брекетинг (без производной)	Метод бисекции Подделки правил метод ИТП
Домохозяин	метод Ньютона метод Галлея
Квазиньютон	метод Бройдена Метод секущего метод Стеффенсена
Гибридные методы	метод Брента Метод рыцарей
Полиномиальные методы	Жертва не удалась Метод Бэрстоу Метод Дюрана – Кернера метод Греффе Алгоритм Дженкинса – Трауба Алгоритм Лемера – Шура метод Лагерра Метод расщепления круга
Другие методы	Итерация с фиксированной точкой Обратная квадратичная интерполяция метод Мюллера Обобщенный метод секущих Сиди