demsp 2 мар 2019 в 09:35

К статье о приближениях

7 мин

7.6K

Занимательные задачкиПрограммирование*Математика*

Часть I
Часть II

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

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

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

Предположим, что цена за одну единицу товара может колебаться в пределах от 5 до 10 RUB. Для двух единиц товара оценка сверху составляет 10+10=20 RUB, оценка снизу 5+5=10 RUB.

Рассмотрим задачу из задачника профильной направленности М.И. Башмакова
37. Известны оценки для переменных $inline$ и $inline$

Дайте оценки сверху для следующих выражений:
1. $inline$
2. $inline$

5. $\frac{ 1 }{y}$
6. $\frac{ x }{y}$

8. $inline$
9. $inline$

Указание к решению задач

Для оценки этих значений необходимо воспользоваться следующим свойством числовых неравенств:
Если $inline$ и оба числа положительны, то $inline$
Если $inline$ и оба числа положительны, то $\frac{ 1 }{a}>\frac{ 1 }{b}$
При умножении членов неравенства на одно и то же положительное число смысл неравенства не меняется, при умножении членов неравенства на одно и то же отрицательное число смысл неравенства меняется на противоположный.
Доказательство (Элементарная математика).
Пусть $inline$ , тогда $inline$ . Если $inline$ , то $inline$ , так как произведение положительных чисел положительно. Раскрыв скобки в левой части последнего неравенства, получим $inline$ , т.е. $inline$ . Аналогичным образом рассматривается случай $inline$ .
Точно такой же вывод можно сделать и относительно деления частей неравенства на какое-либо отличное от нуля число, так как деление на число $n \neq 0$ равносильно умножению на число $inline$ , а числа $inline$ и $inline$ имеют одинаковые знаки.

Вообще, анализ бесконечно малых величин использует критерий оценки. А модуль (как окрестность) присутствует в самом определении предела последовательности.

Последовательность {a $_{n}$ } называется сходящейся к числу a, если для любого $\epsilon >0$ найдётся такое число N (зависящее от $\epsilon$ ), что при $n \geqslant N$ выполняется неравенство $\left| a_{n} - a \right| < \epsilon$

Определение эпсилон-окресности на примере радиоактивонго распада приводится в учебнике «Математический анализ. Учебное пособие для IX — X классов»

Процесс радиоактивного распада. Часто встречаются последовательности, которые «устанавливаются» лишь приближенно—все члены этих последовательностей, начиная с некоторого номера, весьма мало отличаются от некоторого числа a.
Рассмотрим процесс радиоактивного распада. Предположим, что мы взяли кусок радиоактивного вещества весом в 1024 г, причем за одни сутки вес вещества уменьшается в результате распада вдвое. Будем взвешивать наш кусок на весах, чувствительность которых равна 10 г. Вес вещества (если измерения производятся каждые сутки) дает последовательность

$1024, 512, 256, 128, 64, 32,16, 8, 4, 2, 1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, ... (1)$

Ясно, что по истечении 7 суток, когда вещества осталось 8 г, весы с чувствительностью 10 г не дадут нам возможности отличить истинное положение вещей (наличие 8 г вещества) от полного отсутствия данного вещества.
Возьмем более точные весы, имеющие чувствительность в 1 г. Эти весы покажут, что после 7 суток вещество еще осталось. Но после 11 суток (когда вещества остается $\frac{1}{2}$ г) и с их помощью не удается выяснить, есть еще вещество или нет. А весы с чувствительностью в 0,1 г покажут отсутствие вещества лишь по истечении 14 суток (когда на самом деле его останется $\frac{1}{16}$ г). И какой бы чувствительности весы мы ни взяли, наступит момент, начиная с которого мы не сможем выяснить с их помощью, осталось вещество или нет.
Итак, последовательность чисел (1) обладает следующим свойством: какое бы число $\epsilon > 0$ мы ни взяли (то есть какой бы чувствительности весы мы ни взяли), найдется номер N, начиная с которого члены последовательности отличаются от нуля меньше, чем на $\epsilon$ .

Определение бесконечеого ряда

Пусть задана некоторая бесконечная последовательность чисел:

$a_{1},a_{2},a_{3}, ..., a_{n},...$

…
Станем последовательно складывать члены ряда, составляя (в бесконечном количестве) суммы

$A_{1}=a_{1}, A_{2}=a_{1}+a_{2}, A_{3}=a_{1}+a_{2}+a_{3}, A_{n}=a_{1}+a_{2}+...+a_{n}$

Их называют частичными суммами ряда.
Конечный или бесконечный предел А частичной суммы при $n \to \infty$

$A = \lim A_{n}$

называют суммой ряда…
Если в ряде отбросить первые m членов, то получится ряд:

$a_{m+1}+a_{m+2}+...+a_{m+k}+...=\sum\limits_{n=m+1}^{\infty} a_{n}$

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

Вернёмся к задаче
38. Вычислить сумму

$\frac{ 1 }{ 1\cdot2 } + \frac{ 1 }{ 2\cdot3 } + \frac{ 1 }{ 3\cdot4 } + ... + \frac{ 1 }{ 99\cdot100 }$

Ряд $\frac{ n }{ n+1 }$ ограничен сверху. К вопросу о верних и нижних оценках вернёмся после.

Отбросим первое слагаемое $\frac{ 1 }{ 1\cdot2 }$ и рассчитаем, чему равен остаток ряда после первого члена

Код

(define series_sum_1
 ( lambda (n)
  (if (= n 0) 0 
    (+ (/ 1.0 (* (+ n 1.0 )(+ n 2.0))) (series_sum_1(- n 1.0)))
  ) ) )
(writeln (series_sum_1 10))
(writeln (series_sum_1 100))
(writeln (series_sum_1 1000))
(writeln (series_sum_1 10000))
(writeln (series_sum_1 100000))
(writeln (series_sum_1 1000000))

0.41666666666666663
0.49019607843137253
0.4990019960079833
0.4999000199960005
0.49999000019998724
0.4999990000019941
Проверить можно в ideone.com здесь

Этот же алгоритм на Python

def series_sum(n):
	if n==0:
		return 0
	else:
		return 1.0/((n+1.0)*(n+2.0))+series_sum(n-1.0)
 
print(series_sum(10))
print(series_sum(100))

Ссылка на ideone.com

Получим $1 - \frac{ 1 }{ 1\cdot2 } = \frac{ 1 }{ 2}$

Отбросим первое и второе слагаемые и рассмотрим остаток ряда.

Код

(define series_sum_1
 ( lambda (n)
  (if (= n 0) 0 
    (+ (/ 1.0 (* (+ n 2.0) (+ n 3.0))) (series_sum_1(- n 1.0)))
  ) ) )
(series_sum_1 1000000)

Получим 0.33333233333632745
Если ряд сходится, то сумма его остатка после m-го члена с возрастанием m стремится к нулю.
У нас сумма остатка с возрастанием m стремится к нулю.

Верхняя и нижняя оценка

Рассмотрим пример из «Курса дифференциального и интегрального исчисления» 363(6)

Легко установить расходимость ряда

$\sum \frac{ 1 }{\sqrt{n} } = 1+\frac{ 1 }{\sqrt{2}}+ \frac{ 1 }{\sqrt{3}} + ... + \frac{ 1 }{\sqrt{n}} + ...$

В самом деле, так как члены его убывают, то n-я частичная сумма

$1+\frac{ 1 }{\sqrt{2}}+...+ \frac{ 1 }{\sqrt{n}}>n\cdot\frac{ 1 }{\sqrt{n}}= \sqrt{n}$

и растёт до бесконечности вместе с $inline$ .

Для того, чтобы доказать, что $1+\frac{ 1 }{\sqrt{2}}+...+ \frac{ 1 }{\sqrt{n}}$ действительно больше $\sqrt{n}$ , нужно произвести оценку снизу данного выражения. Получим систему неравенств

$\left\{\!\begin{aligned} & \frac{ 1 }{\sqrt{n-1}} > \frac{ 1 }{\sqrt{n}} \\ & \frac{ 1 }{\sqrt{n-2}} > \frac{ 1 }{\sqrt{n}} \\ & \frac{ 1 }{\sqrt{n-3}} > \frac{ 1 }{\sqrt{n}} \\ & ... \end{aligned}\right.$

Произведя сложение всех неравенств данной системы, получим

$1+\frac{ 1 }{\sqrt{2}}+ \frac{ 1 }{\sqrt{3}} + ... + \frac{ 1 }{\sqrt{n}} > \frac{ 1 }{\sqrt{n}} +\frac{ 1 }{\sqrt{n}} + \frac{ 1 }{\sqrt{n}} +...+ \frac{ 1 }{\sqrt{n}} = n\cdot\frac{ 1 }{\sqrt{n}}$

Следовательно, данный ряд расходится.

Для гармонического ряда этот метод не проходит, потому что $inline$ -я частичная сумма гармонического ряда

$1+\frac{ 1 }{2}+ \frac{ 1 }{3} + ... + \frac{ 1 }{n} > n\cdot\frac{ 1 }{n} =1$

Подсчитаем сумму гармонического ряда при увеличении n

#lang racket
(define series_sum_1
 ( lambda (n)
  (if (= n 0) 0 
    (+ (/ 1.0 n) (series_sum_1(- n 1.0)))
  ) ) )
(series_sum_1 10)
(series_sum_1 100)
(series_sum_1 1000)
(series_sum_1 10000)
(series_sum_1 100000)
(series_sum_1 1000000)

Получим:
2.9289682539682538
5.187377517639621
7.485470860550343
9.787606036044348
12.090146129863335
14.392726722864989

Воспользуемся частичными суммами для того, чтобы установить, что сумма гармонического ряда неограничена сверху и растёт до бесконечности

Имеем очевидное неравенство:

$\frac{ 1 }{ n+1 }+\frac{ 1 }{ n+2 }+...+\frac{ 1 }{ 2n }>\frac{ 1 }{ 2 }$

Если, отбросив первые два члена, остальные члены гармонического ряда разбить на группы по $2,4,8,...,2^{k-1},...$ членов в каждой

$\frac{ 1 }{ 3 }+\frac{ 1 }{ 4 }; \frac{ 1 }{5 }+\frac{ 1 }{ 6 }+\frac{ 1 }{7 }+\frac{ 1 }{8 }; \frac{ 1 }{9 }+...\frac{ 1 }{16 };...;$

$\frac{ 1 }{ 2^{k-1}+1 }+...+\frac{ 1 }{ 2^{k} }; ... ,$

то каждая из этих сумм в отдельности будет больше $\frac{ 1 }{ 2 }$ .
… Мы видим, что частичные суммы не могут быть ограничены сверху: ряд имеет бесконечную сумму.

Подсчитаем частичные суммы, которые получаются при отбрасывании $2^{k}$ слагаемых.

Рекурсивный алгоритм

#lang racket
(* 1.0 (+ 1/3 1/4))
(* 1.0 (+ 1/5 1/6 1/7 1/8))
(* 1.0 (+ 1/9 1/10 1/11 1/12 1/13 1/14 1/15 1/16))

Получаем:
0.5833333333333334
0.6345238095238095
0.6628718503718504
Напишем программу, которая вычисляет сумму гармонического ряда от $\frac{n}{2}$ до $inline$ , где $n = 2^{k}$ при $k \in \mathbb{N}$

#lang racket
(define (Hn n )
  (define half_arg (/ n 2.0))  

(define (series_sum n)
  (if (=  n half_arg ) 0 
    (+ (/ 1.0  n) (series_sum(- n 1)) )
  )  
 )
 (series_sum n)   )

(Hn 4)
(Hn 8)
(Hn 16)
(Hn 32)

Проверить можно в online ide по ссылке

Получаем:
0.5833333333333333
0.6345238095238095
0.6628718503718504
0.6777662022075267
Для диапазона $\left[ 1+2^{70};2^{71}\right]$ получаем 0,693147…
Проверить моджно в Wolfram Cloud здесь.

Переполнение стека

Данный рекурсивный алгоритм вызывает быстрое переполнение стека.
В этой статье есть пример вычисления факториала с помощью итеративного алгоритма. Изменим этот итеративный алгоритм так, чтобы он вычислял частичную сумму Hn внутри определённых границ; назовём эти границы a и b

(define (Hn a b)
  (define (iteration product counter)
    (if (> counter b)
        product 
        (iteration (+ product (/ 1.0 counter))
                   (+ counter 1))))
  (iteration 0 a))

Нижней границей является число $1+2^{k}$ , верхней границей — число $2 \cdot 2^{k}$
Напишем функцию, вычисляющую степень двойки

(define (power_of_two k)
  (define (iteration product counter)
    (if (> counter k)
        product
        (iteration (* product 2)
                   (+ counter 1))))
  (iteration 1 1))

Будем в качестве нижней границы подставлять (+ 1 (power_of_two k)), а в качестве верхней можно использовать функцию (* 2 (power_of_two k)) или эквивалентную ей функцию (power_of_two (+ 1 k))
Перепишем функцию Hn

(define (Hn k)
  (define a (+ 1 (power_of_two k)) )
  (define b (* 2 (power_of_two k)) )
    
  (define (iteration product counter)
    (if (> counter b)
        product 
        (iteration (+ product (/ 1.0 counter))
                   (+ counter 1))))
  (iteration 0 a ))

Теперь можно вычислять Hn при больших значениях $inline$ .

Напишем на языке Си программу, которая замеряет время, необходимое на вычисление Hn. Будем использовать функцию clock() из стандартной библиотеки <time.h>
Статья про измерение процессорного времени есть на Хабре здесь.

#include <math.h>
#include <stdio.h>
#include <time.h>
int main(int argc, char **argv)
{
double count; 
// k от 1+2^30 до 2^31
for(unsigned long long int i=1073741825  ;i<=2147483648 ;i++)
{
	count=count+1.0/i;
		}
printf("Hn = %.12f ", count);

 double seconds = clock() / (double) CLOCKS_PER_SEC;
 printf("Программа работала %f сек \n", seconds);
 return 0;
}

Обычно online ide ограничивают время выполнения запускаемых программ пятью секундами, поэтому эту программу можно проверить лишь в некоторых online ide, например, в onlinegdb.com или repl.it
При k от 1+2^30 до 2^31 время работы составит ~5 сек.
При k от 1+2^31 до 2^32 время работы составит ~10 сек.
При k от 1+2^32 до 2^33 время работы составит ~20 сек.
При k от 1+2^33 до 2^34 время работы составит ~40 сек.
При k от 1+2^34 до 2^35 время работы составит больше одной минуты.
…
При k от 1+2^45 до 2^46 время работы составит больше 24 часов.

Предположим, что для k от 1+2^30 до 2^31 время выполнения алгоритма составляет ~2 сек.
Тогда для k=2^(30+n) время выполнения алгоритма составляет 2^n сек. (при $n \in \mathbb{N}$ )
Данный алгоритм имеет экспотенциальную сложность.

Вернёмся к модулям.
В интегральном исчислении модуль используется в формуле

$\int \frac{1}{x} dx = \int \frac{dx}{x} = ln \left| x \right| + C$

Читайте также Самый натуральный логарифм.

Присутствие модуля в формуле $\int \frac{dx}{x} = ln \left| x \right| + C$ обосновывается далее в «Курсе дифференциального и интегрального исчисления»

Если… $inline$ , то дифференцированием легко убедиться в том, что $\left[ ln (-x) \right]' = \frac{1}{x}$

Физическое приложение интеграла $\int \frac{dx}{x}$

Этот интеграл используется для вычисления разности потенциалов обкладок цилиндрического конденсатора.

«Электричество и магнетизм»:

Разность потенциалов между обкладками находим путем интегрирования:

$\varphi_{1}- \varphi_{2} = \int\limits_{R_{1}}^{R_{2}} E(r) dr = \frac{q}{2 \pi \varepsilon_{0} \varepsilon l} \int\limits_{R_{1}}^{R_{2}} \frac{dr}{r} = \frac{q}{2 \pi \varepsilon_{0} \varepsilon l} ln \frac{R_{2}}{R_{1}}$

( $R_{1}$ и $R_{2}$ — радиусы внутренней и внешней обкладок).

Здесь не используется знак модуля под знаком натурального логарифма $ln \left| \frac{R_{2}}{R_{1}} \right|$ , потому что $R_{1}$ и $R_{2}$ строго положительны и такая форма записи является избыточной.

«Модульное» рисование

С помощью модулей можно рисовать различные фигуры.

Если в программе geogebra написать формулу $inline$ получим

Можно рисовать более сложные фигуры. Нарисуем, например, «бабочку» в облаке WolframAlpha

$\sum \frac{ \left| x \right| }{n-\left| x \right| }+ \frac{ \left| x+n \right| }{n} + \frac{ \left| x-n \right| }{n}$

Plot[ Sum[abs(x)/(n-abs(x))+abs(x+n)/(n)+abs(x-n)/(n),{n,1,20}], {x,-60,60} ]
В данном выражении n лежит в диапазоне от 1 до 20, x лежит в диапазоне от -60 до 60.
Ссылка на рисунок.

Книги:

«Задачник профильной направленности» М.И. Башмаков
«Элементарная математика» В.В.Зайцев, В.В.Рыжков, М.И.Сканави
«Математический анализ. Учебное пособие для IX — X классов» Виленкин Н.Я., Шварцбурд С.И.
Курс общей физики: в 3-х т. Т. 2. «Электричество и магнетизм» И.В. Савельев

Теги:

Хабы: