Метод половинного деления, зависание

@QuasiSimon · Регистрация: 19.04.2013

Студворк — интернет-сервис помощи студентам

День добрый. Реализовал вот такой макрос решения уравнения методом половинного деления.

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
Sub calc_q()
'
 
 
Application.ScreenUpdating = False
 
Dim b1 As Single
Dim q1 As Single
Dim q2 As Single
 
Dim n As Integer
 
Dim q As Single
Dim s As Single
 
b1 = Range("B1")
s = Range("B2")
n = Range("B3")
q1 = Range("B4")
q2 = Range("B5")
 
q = 1.1
 
   
Do While Abs(b1 * (1 - q ^ n) / (1 - q) - s) > 0.01
 
    If (b1 * (1 - q ^ n) / (1 - q) - s) < 0 Then
        q1 = q
        q = (q1 + q2) / 2
    Else
        q2 = q
        q = (q2 + q1) / 2
    End If
        
Loop
 
Range("E3") = q
 
Application.ScreenUpdating = True
 
End Sub

Но при изменении точности расчета (0.01 в условии DoWhile) макрос стопит весь эксель. Причем изменение точности на порядок, не приводит к большим затратам по вычислениям (проверено в матлабе). Вопрос - в чем может быть причина зависания?

@Казанский · 25.10.2017, 14:51

QuasiSimon, странное условие в Do While. Обычно

Visual Basic
1
Do While q2 - q1 > 0.01

@QuasiSimon · 25.10.2017, 15:06 **[ТС]**

Не спорю, но вдруг я найду истинный корень, при котором уравнение (b1 * (1 - q ^ n) / (1 - q) - s) равно нулю? Тогда истинное значение от меня уйдет, так как разница между q1 q1 может быть большой

@Burk · 25.10.2017, 23:36

QuasiSimon, такие коды лучше не посылать. Ну откуда нам известны значения, хранящиеся в ячейках В1-В5???
Может при этих параметрах функция не имеет корней, что вполне вероятно. Надо писать, например b1=7 и т.д.

Добавлено через 33 минуты
QuasiSimon, да и вообще такой алгоритм половинного деления неверен. функция от q1 может быть как положительна, так и отрицательна и в зависимости от этого присвоение q либо левая, либо правая половина отрезка.
Еще - при q =0 F=b1/(1-s) если s<1, то F>0. При q=1/1 А>0 тоже????
Половинное деление делается так: сначала с постоянным шагом идем по функции и ищем интервал, где функция меняет знак, а уж потом деление пополам, в зависимости от знака функции на левой или правой границе интервала. Да и чисто по программистски надо описать функцию, чтобы два раза ее не считать как значение и как условие.

@QuasiSimon · 26.10.2017, 07:14 **[ТС]**

Сообщение от Burk

да и вообще такой алгоритм половинного деления неверен. функция от q1 может быть как положительна, так и отрицательна и в зависимости от этого присвоение q либо левая, либо правая половина отрезка.

Так и делается. q1 - левая граница, q2 - правая.
Для данной задачи изначально были ограничения - q > 1. Поэтому описанные вами варианты и не рассматривались. Плюс интервал задается оператором (как видно из кода значения границ берутся из ячеек).

Сообщение от Burk

Ну откуда нам известны значения, хранящиеся в ячейках В1-В5???

Это не спорю, моя ошибка, торопился просто.

Вообще сделал условие

Сообщение от Казанский

q2 - q1 > 0.01

И все заработало, видимо постоянное вычисление степени в условии его вешало.

@Burk · 26.10.2017, 13:36

QuasiSimon, ну это вам повезло, что ваша функция возрастающая от минуса к плюсу, если бы было наоборот, то ваш бы алгоритм не сработал, правильно так

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Private B As Double, N As Integer, S As Double, q As Double
Private Function Fq(q As Double) As Double
Fq = B * (1# - q ^ N) / (1# - q) - S
End Function
Private Sub OneHalf()
'условие существования нуля функции на участке q > 1 b*N < S
Dim q1 As Double, q2 As Double, Znak As Integer, F As Double
N = 3: B = 5#: S = 20#
q2 = 1.01: F = Fq(q2): Znak = Sgn(F)
Do  'находим участок, где функция меняет знак
  q2 = q2 + 0.1: F = Fq(q2)
Loop Until F * Znak < 0
q1 = q2 - 0.1: q = q1 + 0.05
Do
  If Znak * Fq(q) < 0 Then q2 = q Else q1 = q
  q = (q1 + q2) / 2
Loop Until q2 - q1 < 0.001
MsgBox "q=" & q & "  f=" & Fq(q)
End Sub

Я тут исследовал вашу функцию и получил условие существования ее нуля (в тексте кода). Вроде не ошибся, проверил на конкретных числах. S, N, B замените на свои ячейки

Добавлено через 33 минуты
QuasiSimon, кстати, то что вы заменили условие выхода из цикла, это ни о чем не говорит, просто ваш q сходится к неправильному значению. Вы ведь не выводили функцию? При правильном алгоритме и оно бы сработало. Для половинкина деления оно более верное. Есть гарантия, что нашли ноль функции. А так, естественно, делим неправильный интервал пополам. и получаем выход из цикла при параметре далеком от нуля функции

Добавлено через 4 часа 59 минут
QuasiSimon, еще хочу добавить из анализа функции
если b < S и b*n > S то ноль функции будет на промежутке 0 - 1, при этом для q > 1 нуля не будет. Ну и что я писал ранее
при b*n < S ноль функции будет при q > 1, а на 0 - 1 нуля не будет. В остальных случаях нуля не будет нигде

@QuasiSimon · 27.10.2017, 07:24 **[ТС]**

Спасибо за такое подробное участие).
Но есть пара возражений:
1) замена условия как раз такие находит окрестность, которая ближе всего к нулю функции. ПРоблема в том, что при больших N вычислить точное значение q при котором функция равна нулю, практически невозможно, там нужно соблюсти точности знака после запятой порядка 10^12. А это долго, да и не нужна нам такая точность.
2) В моем варианте интервал всегда верный (повторюсь, было жесткое условие задачи что q всегда > 1). В вашем варианте мне не понравилось, что поиск нуля идет с фиксированным шагом, это может ооочень затянуть вычисления, если к примеру наша верхняя граница находится на огромных значениях. А при поиске методом половинного деления определяющим является задание верхней и нижней границы, причем какое бы значение не задали, поиск идет быстро, так как практически всегда идет /2.
3) Условие b < S и b*n > S тоже не может быть, так как это приводит (в принципе уже наверняка поняли из выше описанного), что q < 1.

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

@Burk · 27.10.2017, 09:00

QuasiSimon, я с вами не веду дискуссию, а объясняю как надо делать. Я на этом деле хоть маленькую, но собаку съел. Вы рассуждаете так, как будто вычисления проводите на ручном калькуляторе (были такие Феликсы, на которых надо ручку крутить), а работаете с компом, тактовая частота которого ГИГАГЕРЦЫ! У вас ЗАВИСАЕТ не потому, что не может вычислить долго q^n - это делается в доли микросекунд, а то, что вы находитесь в области, где нет нуля, поэтому ваш цикл бесконечен - нуля функции просто не на этом интервале. Г-н Казанский подсказал вам неверный метод выхода из цикла, не учтя всё, что я писал, а вы и радуетесь. Не нравится постоянный шаг 0,1 поставьте 10 или 100 и запустите мой Саб. Только в начале его поставьте следующие операторы, чтобы опять не зациклило, а то будете говорить, что и моя программа ЗАВИСАЕТ

Visual Basic
1
2
3
4
If b * n >= S then
  Msgbox "Нуля функции не существует при этих параметрах"
  Exit Sub
End If

и в сою программу поставьте эти операторы, чтобы не искать черную кошку в тёмной комнате, если ее там и нет /фильм Место встречи изменить нельзя/

Сообщение от QuasiSimon

в принципе уже наверняка поняли из выше описанного

Мне ничего понимать не нужно из ваших рассуждения, они от, пока ещё, незнания.
Чего проще - запустить мой Саб, и даже с шагом 0.1 глазом моргнуть не успеете, как всё будет готово.
Нужно делать так, как я написал, и никак иначе. А если хотите ускорить сходимость к нулю функции, то воспользуйтесь методом Ньютона q_i+1 = q_i - F/F' F -ваша функция, F' - производная от неё

Добавлено через 26 минут
QuasiSimon, а ещё лучше, чтобы распространить поиск на интервал от нуля, условие из предыдущего послания записать так

Visual Basic
1
If b * n >= S Or Not (b < S And b*n > S)) Then

и тогда вместо q2 = 1.01 поставить, например, q2 = 0.001, можно поставить и ноль, но тогда шаг поиска сделать таким, чтобы не налететь на q = 1, например, 0.7

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@QuasiSimon 1 / 1 / 0 Регистрация: 19.04.2013 Сообщений: 93
	25.10.2017, 15:06 [ТС]
	Не спорю, но вдруг я найду истинный корень, при котором уравнение (b1 * (1 - q ^ n) / (1 - q) - s) равно нулю? Тогда истинное значение от меня уйдет, так как разница между q1 q1 может быть большой 0

@Burk 1847 / 1162 / 354 Регистрация: 11.07.2014 Сообщений: 4,107
	25.10.2017, 23:36
	QuasiSimon, такие коды лучше не посылать. Ну откуда нам известны значения, хранящиеся в ячейках В1-В5??? Может при этих параметрах функция не имеет корней, что вполне вероятно. Надо писать, например b1=7 и т.д. Добавлено через 33 минуты QuasiSimon, да и вообще такой алгоритм половинного деления неверен. функция от q1 может быть как положительна, так и отрицательна и в зависимости от этого присвоение q либо левая, либо правая половина отрезка. Еще - при q =0 F=b1/(1-s) если s<1, то F>0. При q=1/1 А>0 тоже???? Половинное деление делается так: сначала с постоянным шагом идем по функции и ищем интервал, где функция меняет знак, а уж потом деление пополам, в зависимости от знака функции на левой или правой границе интервала. Да и чисто по программистски надо описать функцию, чтобы два раза ее не считать как значение и как условие. 0

@QuasiSimon 1 / 1 / 0 Регистрация: 19.04.2013 Сообщений: 93
	27.10.2017, 07:24 [ТС]
	Спасибо за такое подробное участие). Но есть пара возражений: 1) замена условия как раз такие находит окрестность, которая ближе всего к нулю функции. ПРоблема в том, что при больших N вычислить точное значение q при котором функция равна нулю, практически невозможно, там нужно соблюсти точности знака после запятой порядка 10^12. А это долго, да и не нужна нам такая точность. 2) В моем варианте интервал всегда верный (повторюсь, было жесткое условие задачи что q всегда > 1). В вашем варианте мне не понравилось, что поиск нуля идет с фиксированным шагом, это может ооочень затянуть вычисления, если к примеру наша верхняя граница находится на огромных значениях. А при поиске методом половинного деления определяющим является задание верхней и нижней границы, причем какое бы значение не задали, поиск идет быстро, так как практически всегда идет /2. 3) Условие b < S и b*n > S тоже не может быть, так как это приводит (в принципе уже наверняка поняли из выше описанного), что q < 1. Но да, в вашем случае исключен вариант, что мы неверно задали границы поиска корня и в этом случае корень будет найден гарантировано. 0