MAXimal

���������: 23 Jul 2009 12:53
�������������: 23 Jul 2009 12:53

���������� [������]

��������� �����

���������� ������

����� ���� ������� f(x), ������������ �� ��������� ������� [l;r]. ��� ��������������� ���������� ���� �� ���� ���������. ������: ������� ������� ������ ����������, ����� ��������� ��������� (� ����� ����� ��� ����� �������), ����� ������ �������. ������ �������, ������������: ������� ������� ������� �������, ��������� ��������, ����������. � ���������� �� ����� ������������� ������ �������, ������ ����� ��������� ����������� ���.

��������� ����� �������� ������� f(x) �� ������� [l;r].

��������

������ ����� ��� ����� m_1 � m_2 � ���� �������: l < m_1 < m_2 < r. ��������� �������� ������� f(m_1) � f(m_2). ������ � ��� ���������� ��� ��������:

  • ���� ��������, ��� f(m_1) < f(m_2), �� ������� �������� �� ����� ���������� � ����� �����, �.�. � ����� [l;m_1]. � ���� ����� ���������: ���� � ����� ����� ������� ������, ��� � ������, �� ���� ��� ��� ����� ��������� � ������� "�������" �������, ���� ������ ����� ����� ��������� ���. � ����� ������, ��� ��������, ��� �������� ������ ����� ����� ������ ������ � ������� [m_1;r].

  • ����, ��������, f(m_1) > f(m_2), �� �������� ���������� ���������� � ��������� �� ���������. ������ ������� �������� �� ����� ���������� � ������ �����, �.�. � ����� [m_2;r], ������� ��������� � ������� [l;m_2].

  • ���� f(m_1) = f(m_2), �� ���� ��� ��� ����� ��������� � ������� ���������, ���� ����� ����� ��������� � ������� �����������, � ������ — � ������� �������� (����� ����������� ������������ ��, ��� �����������/�������� �������). ����� �������, � ���������� ����� ����� ����� ����������� � ������� [m_1;m_2], �� (� ����� ��������� ����) ���� ������ ����� ������� � ������ �� ���� ����������.

����� �������, �� ���������� ��������� �������� ������� � ���� ���������� ������ �� ������ �������� ������� ������ [l;r] ������� ����� ������� [l^\prime;r^\prime]. �������� ������ ��� �������� ��� ����� ������ �������, ����� ������� �����, ������ �������, �������, � �.�.

���� ��� ������ ����� ������� ������ ���������, ������� ������� ����������� ���������-��������, � ������� ����� �������������. ���� ����� ���������, ������� ����� ��������� ��������� ����� ���������� �������, ��� �� ���� ������ ������� [l;r] ����������� ��������; � �������� ������ ����� �����, ��������, ����� l.

�������� ��������, ��� �� �� ����������� ������� ����������� �� ����� ����� m_1 � m_2. �� ����� �������, �������, ����� �������� �������� ���������� (�� � ����������� �����������). �������� ���������������� ������ — �������� ����� ���, ����� ������� [l;r] ������� ��� �� 3 ������ �����:

 m_1 = l + \frac{r-l}{3}
 m_2 = r - \frac{r-l}{3}

�������, ��� ������ ������, ����� m_1 � m_2 ����� ���� � �����, �������� ���������� ��������� ����������.

������ �������������� ���������

���� �������� ������� f �������������, �� ������� [l;r] ���� ���������� ����������, ������, ��������� �� �� ����������� ������� ����������� �� ����� ����� m_1 � m_2, �� �� ������������ ��������� ��� ����� �� ������. ����� ��-�������� �������� m_1 � m_2 ���, ����� ��� ������ ������� [l;r] �� 3 �����, �� ��� ������ ������ ��������������.

������ ������������ ������ — �������� ��������� ���������. � ������ ������ ��������� ����� ���� ����� �������������, ����� ������ r-l<3, ���� � ����� ������ ��� ���������� ����� ������� ����� m_1 � m_2 ���, ����� ���� ���������� � ���������� �� l � r, � ��� ����� �������� � ������������. ����� ����, ��� �������� ���������� ������ ����������� � ������ r-l<3, �� ���������� ���������� �����-���������� (l,l+1,\ldots,r) ���� ������� ����� � ������������ ��������� �������.

����������

���������� ��� ������������ ������ (�.�. ������� f ����� ���: \rm double\ f\ (double\ x)):

double l = ..., r = ..., EPS = ...; // ������� ������
while (r - l > EPS) {
   double m1 = l + (r - l) / 3,
      m2 = r - (r - l) / 3;
   if (f (m1) < f (m2))
      l = m1;
   else
      r = m2;
}

����� \rm EPS — ����������, ���������� ����������� ������ (�� ������ ������������, ��������� � �������� ����������� �������).

������ �������� "while (r - l > EPS)" ����� ������� � ����� �������� ��������:

for (int it=0; it<iterations; ++it)

� ����� �������, ������� ��������� ��������� \rm iterations, ����� ���������� ��������� �������� (������ ���������� ���������� �����, ����� ������� ������������ ��������). �� ����, � ������ �������, ����� �������� �������� �������� �� ���������� ������� l � r, �.�. �� ���������� � ������� \rm iterations ����� ��������� ������������� �����������.