В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 2
Текст из файла (страница 2)
Но как быть в случае с представлением чиселв компьютерах, где для представления чисел используются только два символа: 0 и 1?Для указания знака используется один из разрядов числа (старший), причём единица внём соответствует отрицательному знаку числа (в таблице ниже знаковый разряд выделенцветом).Число Двоичный дополнительный код+127...+10−1...−127−1280111 1111...0000 00010000 00001111 1111...1000 00011000 0000Для изменения знака числа в двоичном дополнительном коде нужно выполнить следующиедействия: инвертировать все биты числа (включая и знаковый), а затем прибавить к результату единицу (правда, для числа −128 эта процедура не работает...).71.3.Представление вещественных чиселПредставление вещественных чисел в компьютерах в своей основе опирается на экспоненциальную форму числа, в которой хранятся мантисса и показатель степени (экспонента) вместе со знаком числа, так что образуемое ими число есть± · 2Поскольку в подобном представлении всегда имеется неоднозначность (что мешает нам,например, удвоить, учетверить и т.д.
значение , уменьшив при этом значение экспоненты на единицу, двойку и т.п.?), используется так называемая нормализованная форма такогопредставления, когда 1 ≤ < 2, т.е., считается, что первая цифра мантиссы – всегдаединица, а потому её даже не имеет смысла хранить; в представлении числа хранитсялишь его дробная часть, а единица целой части «подразумевается».Преимущество экспоненциальной формы представления чисел – существенно больший диапазон значений при неизменной относительной точности представления.
Используемые сейчас варианты зафиксированы в стандарте IEEE 754. Для хранения вещественной величиныодинарной точности (в языке C/C++ соответствующий тип данных называется float) отводится 32 бита: 1 – для знака числа , 8 – для экспоненты , 23 – для мантиссы .Вот как, например, будет представлено в этой форме число 1.0:0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0По заполнению указанных здесь полей можно узнать само число, оно будет равно:(−1) · (1 + ) · 2−127 = (−1)0 · (1 + 0.0) · 2127−127 = 1 · 1.0 · 20 = 1.0Обратите внимание, что поле экспоненты хранится со смещением (увеличенное на 127), т.е.,знак экспоненты присутствует неявно; значения 0 и 255 в поле экспоненты используютсяспециальным образом. Они помогают хранить нулевые значения (которые в экспоненциальной форме с ненулевой мантиссой представить невозможно) и некоторые другие полезныезначения.
Среди этих специальных значений имеются: два нулевых значения: +0, −0, двебесконечности +∞ и −∞, а также NaNs – не-числа (сокращение – от английского выражения Not-a-Number ). Целые числа, большие 16 777 216 (224 ) уже не представимы точнои округляются. Предусмотрено 4 режима округления (to Nearest, toward 0, toward +∞,toward −∞).Вещественные величины двойной точности (в языке C/C++ соответствующий тип данныхназывается double) хранятся аналогичным образом. Для их хранения отводится 64 бита:1 – для знака числа, 11 – для экспоненты, 52 – для мантиссы.Из-за фиксированности места для хранения чисел в программах мы сталкиваемся с тем,что: точность представления чисел – ограничена, только некоторые числа представленыточно (все непредставимые заменяются ближайшим представимым); диапазон представления чисел ограничен.8Для вещественных величин типа float наибольшее представимое в таком виде число – порядка1038 , ближайшее к нулю положительное число – порядка 10−38 .
Для вещественных величинтипа double аналогичные величины – порядка 10308 и 10−308 соответственно. Таким образом,очень близкие к нулю положительные величины (то же самое верно и для ближайших к нулюотрицательных величин) становятся неотличимыми в программах от нуля, а потому возникаетпонятие «машинного нуля» – совокупности чисел, эквивалентных в программах нулю, но неравных ему.По этим причинам некоторые вполне привычные операции становятся невозможными, аполучаемые результаты – на первый взгляд совершенно удивительными. В одном из приведённых ниже примеров два вещественных числа разного типа, проинициализированныеодной и той же константой, оказываются не равными друг другу!Причина в том, что число 0.1 – из-за применения двоичной системы – ни в одном из способов не представляется точно, а, значит, используются некоторые приближения к нему, и этиприближения – разные.Во втором примере вычисляется сумма одних и тех же величин, но в разном порядке.Видно, что две суммы заметно различаются в шестом знаке после запятой, хотя точностьвеличин типа float – 7-8 десятичных цифр.Выводы:Вещественные числа в программах не имеет смысла сравнивать на совпаде-ние друг с другом, поскольку такое совпадение практически невозможно.
Погрешностьпри обработке накапливается, а результат вычислений зависит от порядка их исполнения.92.Численное решение уравненийПосле небольшого экскурса в существующие способы представления численной информации в компьютерах посмотрим, как осуществляется численное решение уравнений, причёмс учётом тех особенностей, которые порождаются используемыми способами представления чисел.Напомним, какие особенности имеются в виду: ограниченность диапазона представимых величин (целочисленные, вещественные) неточность представления большинства величин (вещественные) неотличимость некоторых величин от нулевого значения (вещественные)2.1.Метод деления отрезка пополам (метод дихотомии)Пусть () – непрерывная функция и наконцах отрезка [, ] имеет значения разных знаков. Тогда (по теореме Вейерштрасса) она имеет на этом отрезке хотябы один корень.
Найдём его с заданнойточностью . Будем предполагать, что наотрезке он – единственный.Заметим, что непрерывность функции –важна, поскольку иначе корня на отрезке может и не быть. Кроме того, для последующей процедуры важна единственность корня на этом отрезке. Если их будетРис. 1: Метод дихотомиинесколько, то заранее неизвестно, будет линайден один из корней, и, если найден, какой именно, – всё зависит от точной реализации алгоритма и конкретных значений , .Возьмём центральную точку отрезка и сравним знаки функции в точках и . Еслизнаки одинаковы, перейдём к отрезку [, ], если знаки различны – перейдём к отрезку[, ]. Новый отрезок вдвое меньше и на нём точно присутствует корень уравнения, поэтомумы можем повторить процедуру для этой половины отрезка.
В результате будет полученещё меньший отрезок, также содержащий корень. Продолжая аналогичным образом, мыбудем получать всё меньший и меньший отрезок, содержащий неизвестный корень. Но кактолько размеры отрезка станут меньше требуемой величины погрешности определениякорня, можно остановиться и взять в качестве корня любую точку отрезка, скажем, егосередину.Существуют разные алгоритмические реализации такой процедуры; в некоторых из них можно встретить вместо сравнения знаков функции на концах отрезка проверку знака произведения () · (). Однако это хуже сравнения знаков у двух значений функции, т.к. привычислении произведения значений функции вполне может получиться ноль (если оба значения функции будут малы, см.
замечания выше), а тогда правильность поведения алгоритма– под большим вопросом, всё будет зависеть от того, какая конкретно операция сравненияиспользована...10Некоторая неприятность возможна при организации цикла. Проверка малости текущего отрезка | − | < работает хорошо только если сам отрезок находится не слишком «далеко» отнуля.
Поскольку вещественные значения, точно представимые в программе, по мере удалениязначений от нуля располагаются всё реже и реже, при «удалённом» от нуля отрезке можетслучиться так, что такая проверка никогда не даст возможности выйти из цикла, так как всененулевые длины отрезков в области этих значений превышают заданную точность...Напоследок – ещё одна «неожиданность», вполне вероятная при очень малых отрезках (т.е.,тогда, когда мы стремимся найти корень всё точнее и точнее). Формула вычисления серединыотрезка при размерах отрезка, сравнимых с точностью представления чисел, может дать намрезультат, лежащий на границе отрезка либо даже выходящий за пределы отрезка!2.2.Метод хордВ этом методе на интервале [−1 , ],содержащем корень, проводится прямаячерез концы интервала («хорда»).
Точку +1 , где она пересекает ось абсцисс,мы принимаем за очередное приближение к корню. Соотношение между координатами точки , на прямой, проходящей через две точки −1 , −1 = (−1 ) и , = ( ), очевидное из подобия, таково: ( ) − − .= − −1 ( ) − (−1 )Пусть эта прямая пересекает ось абсцисс в точке = +1 , тогда = 0 и,соответственно,Рис.
2: Метод хорд ( ) − +1=, − −1 ( ) − (−1 )откуда+1 = − ( ) · − −1. ( ) − (−1 )Далее можно, как и в методе деления отрезка пополам, выбрать из двух полученных интервалов тот, на котором находится корень, а с ним проделать только описанную процедурупостроения хорды и получить новое приближение к корню. При этом все хорды будутиметь общую точку в одном из концов первоначального отрезка.Существует и другой вариант, когда мы просто после получения +1 из значений , −1 поимеющейся формуле вычисляем +2 по значениям +1 , и принимаем его в качестве следующего приближения. При этом проверка наличия корня на новом интервале не производится,он может лежать и за пределами интервала, а сам вариант метода скорее можно назвать неметодом хорд, а методом секущих.В любом случае повторение процедуры прекращается, если два последовательных приближения к корню уже достаточно близки друг к другу.11Известно, что если () – дваждынепрерывно дифференцируемая функция и знак ′′ () сохраняется на рассматриваемом отрезке, то получаемыеприближения в методе хорд будут сходиться к корню монотонно.2.3.Метод касательныхПредполагается, что () дифференцируема на отрезке, где происходит поисккорня.
Задаётся начальное приближение вблизи предполагаемого корня (илииспользуется приближение предыдущего шага), строится касательная к функции () в этой точке, тогда точка пересечения касательной с осью даёт следующее приближение.Рис. 3: Метод касательныхЗначения , +1 cвязаны уравнением для тангенса угла наклона этой касательной: ′ ( ) = ( ) − 0, − +1откуда получаем явное выражение для +1 через :+1 = − ( ). ′ ( )В этом методе мы тоже останавливаемся тогда, когда два последовательных приближениядостаточно близки друг к другу.Если первоначальное приближение выбрано достаточно близко ккорню, последовательность сходится, причём вблизи корня –монотонно, и с той стороны, с которой () · ′′ () ≥ 0.Возможные неприятности в этом методе (примеры из книгиН.Н.Калиткина): плохо, если корень находится далеко от начального приближения; для уравнения с () = 3 − 2 + 2 начальноеприближение 0 – весьма неудачно, следующее значение приближения в этом методе будет равно 1, затем снова 0, и т.д.,следовательно, корень никогда не будет найден; плохо, если производная в точке корня равна нулю; самыйтривиальный пример – () = 2 .2.4.Рис.
4: «Плохой»выбор начальногоприближенияМетод итерацийУравнение () = 0 заменяется равносильным, но вида = (), и строится последовательность значений , такая, что +1 = ( ), = 0, 1, 2, . . ., т.е., последующее значениеполучается из предыдущего с помощью функции . Если () определена и дифференцируема на некотором интервале, причём | ′ ()| < 1, то тогда последовательность сходится12к корню уравнения на этом интервале. Иллюстрирующие этот процесс сходимости картинки приведены ниже.(a) Возрастающая функция ()(b) Убывающая функция ()Рис. 5: Метод итераций: разные типы сходимости к корню уравненияОбратите внимание на то, что характер сходимости определяется знаком производной ′ ().Таким образом, во всех разобранных методах удаётся построить последовательность приближений к неизвестному корню (в методе дихотомии эта последовательность – неявная, нов качестве неё можно взять, например, последовательность середин получаемых на каждомшаге отрезков), которая к корню сходится.133.Вычисление определённых интеграловРассмотрим задачу о приближённом нахождении значения интеграла=∫︁ () Относительно () будем предполагать, что она непрерывна на [, ], а также – когда понадобится, – что она имеет на этом отрезке производные до некоторого порядка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
