Помогите решить уравнение

[vlad_light]

Даны все $\{X_i, Y_i, \sigma _i| i=\overline {1,n}\}$, и имеется явный вид для формул $m(X), v(X)$. Как найти параметр $\beta$ в следующем уравнении?

$$\sum\limits _{i=1}^n\frac{Y_i-\beta m(X_i)}{\beta ^2v(X_i)+\sigma _i^2}m(X_i)=0$$

Явного вида скорее всего не получится, хотя бы алгоритм подскажите. ($n$ - очень большое)

[Cash]

Что в вашем понимании очень большое? Тысяча? Миллион? Квадриллион?
Порядок скажите...

[vlad_light]

до миллиона, где-то 10.000-100.000

[Cash]

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

[vlad_light]

Написал методом половинного деления -- работает очень медленно. Начиная с 2000 считает около 10 секунд. Очень долго каждый раз вручную пересчитывать такую сумму. Кто ещё подскажет что-то?

[Pphantom]

vlad_light в сообщении #658908 писал(а):

Написал методом половинного деления -- работает очень медленно. Начиная с 2000 считает около 10 секунд. Очень долго каждый раз вручную пересчитывать такую сумму. Кто ещё подскажет что-то?

По-видимому, Вы как-то очень неудачно написали дихотомию. Сейчас интереса ради набросал эту программу (для случайных данных) - для $n=10^6$ с итоговой погрешностью $10^{-8}$ счет занимает 0.1 секунды (на одном ядре приличного, но вполне обычного процессора).

[vlad_light]

Сколько времени считает одну итерацию?

1. #include <iostream> 
2. #include <random> 
3. #include <cstdlib> 
4. #include <ctime> 
5.  
6. const int SAMPLE_SIZE = 1000; 
7. const double PRECISION = 0.01; 
8.  
9. const double MU_TEST = -240.3; 
10. const double SIGMA_TEST_SQUARED = 591.7; 
11. const double BETA_TEST = 45.6; 
12.  
13. const double SIGMA_EPSILON_SQUARED = 7.6; 
14. const double SIGMA_DELTA_SQUARED = 1.8; 
15.  
16. double Box_Muller (); 
17. void init_sample (double* sample_x, double* sample_y); 
18.  
19. double sample_mean (const double* sample_x); 
20. double sample_squared_variance (const double* sample_x); 
21.  
22. double sum_Q (const double* sample_x, const double* sample_y, const double beta); 
23. double dichotomy_method (const double epsilon, const double a, const double b, const double* sample_x, const double* sample_y); // or any other solver 
24.  
25. int main () 
26. { 
27. srand (time (NULL)); 
28.  
29. double sample_X[SAMPLE_SIZE], sample_Y[SAMPLE_SIZE]; 
30.  
31. init_sample (sample_X, sample_Y); 
32.  
33. std::cout << dichotomy_method (PRECISION, -1000, 1000, sample_X, sample_Y); 
34.  
35. std::cin.get (); 
36. return 0; 
37. } 
38.  
39. double Box_Muller () 
40. { 
41. do 
42. { 
43. double r_1 = rand (); 
44. r_1 = (r_1 / RAND_MAX - 0.5) * 2; 
45. double r_2 = rand (); 
46. r_2 = (r_2 / RAND_MAX - 0.5) * 2; 
47.  
48. double s = r_1 * r_1 + r_2 * r_2; 
49.  
50. if (s > 0 && s <= 1) 
51. return r_1 * std::sqrt (-2 * std::log (s) / s); 
52. } 
53. while (true); 
54. } 
55.  
56. void init_sample (double* sample_x, double* sample_y) 
57. { 
58. for (int i = 0; i < SAMPLE_SIZE; ++i) 
59. { 
60. const double EPSILON = std::sqrt (SIGMA_EPSILON_SQUARED) * Box_Muller (); 
61. const double DELTA = std::sqrt (SIGMA_DELTA_SQUARED) * Box_Muller (); 
62.  
63. const double X = MU_TEST + std::sqrt (SIGMA_TEST_SQUARED) * Box_Muller () + DELTA; 
64. const double Y = BETA_TEST * (MU_TEST + std::sqrt (SIGMA_TEST_SQUARED) * Box_Muller ()) *  
65. (MU_TEST + std::sqrt (SIGMA_TEST_SQUARED) * Box_Muller ()) + EPSILON; 
66.  
67. sample_x[i] = X; 
68. sample_y[i] = Y; 
69. } 
70. } 
71.  
72. double sample_mean (const double* sample_x) 
73. { 
74. double mean = 0; 
75.  
76. for (int i = 0; i < SAMPLE_SIZE; ++i) 
77. mean += sample_x[i]; 
78.  
79. return mean / SAMPLE_SIZE; 
80. } 
81.  
82. double sample_squared_variance (const double* sample_x) 
83. { 
84. const double mean = sample_mean (sample_x); 
85.  
86. double variance = 0; 
87.  
88. for (int i = 0; i < SAMPLE_SIZE; ++i) 
89. variance += (sample_x[i] - mean) * (sample_x[i] - mean); 
90.  
91. return variance / (SAMPLE_SIZE - 1) - SIGMA_DELTA_SQUARED; 
92. } 
93.  
94. double sum_Q (const double* sample_x, const double* sample_y, const double beta) 
95. { 
96. double sum = 0; 
97.  
98. for (int i = 0; i < SAMPLE_SIZE; ++i) 
99. { 
100. const double left_summand = (sample_mean (sample_x) * SIGMA_DELTA_SQUARED + sample_x[i] * sample_squared_variance (sample_x)) /  
101. (SIGMA_DELTA_SQUARED + sample_squared_variance (sample_x)) *  
102. (sample_mean (sample_x) * SIGMA_DELTA_SQUARED + sample_x[i] * sample_squared_variance (sample_x)) /  
103. (SIGMA_DELTA_SQUARED + sample_squared_variance (sample_x)); 
104. const double right_summand = SIGMA_DELTA_SQUARED * sample_squared_variance (sample_x) / (SIGMA_DELTA_SQUARED + sample_squared_variance (sample_x)); 
105.  
106. const double dm = left_summand + right_summand; 
107.  
108. const double v = beta * beta * (4 * left_summand * right_summand + 2 * right_summand * right_summand) + SIGMA_EPSILON_SQUARED; 
109.  
110. sum += (sample_y[i] - beta * dm) * dm / v; 
111. } 
112.  
113. return sum; 
114. } 
115.  
116. double dichotomy_method (const double epsilon, const double a, const double b, const double* sample_x, const double* sample_y) 
117. { 
118. double new_a = a, new_b = b; 
119.  
120. while (std::abs (new_a - new_b) > epsilon) 
121. { 
122. const double c = (new_a + new_b) / 2; 
123.  
124. if (sum_Q (sample_x, sample_y, new_a) * sum_Q (sample_x, sample_y, c) < 0) 
125. new_b = c; 
126. else 
127. new_a = c; 
128.  
129. std::cout << c << std::endl; 
130. } 
131.  
132. return (new_a + new_b) / 2; 
133. } 

[Pphantom]

vlad_light в сообщении #658943 писал(а):

Сколько времени считает одну итерацию?

Поскольку начальный интервал имел размер $10^1$, а в итоге сократился до $10^{-8}$, то это 30 итераций. Дихотомия же.

Так... послушайте, а зачем Вы при каждом вычислении суммы заново считаете все $m(X_i)$ и $v(X_i)$? И зачем при выборе правого или левого отрезка заново пересчитываете значение суммы в new_a? Да, Вы "идеологически правильно" разнесли все по куче функций без глобальных переменных, но именно это и привело к такой безумной потере производительности.

[Cash]

Вместо функций sample_mean и sample_squared_variance сделайте 2 массива. Этого будет достаточно. Сложность сразу сократится с $O(n^2)$ до $O(n)$. Все остальное уже мелочи.

[vlad_light]

Всем большое спасибо, учёл все комментарии -- работает за 0.1 сек Ещё раз спасибо!

(Оффтоп)

Не будет из меня програмиста