Let
$$R=\left\{(x,y):-1\le x\le 1,\ 0\le y\le 1-x^4\right\}.$$
We want the largest-area \(n\)-gon contained in this region for \(n=101\). The implementations represent the polygon by ordered boundary points
$$-1=x_0<x_1<\cdots<x_{n-1}=1,$$
with vertices
$$P_i=\left(x_i,\,1-x_i^4\right).$$
Because \(1-x^4\) is concave on \([-1,1]\), every chord between two such boundary points stays below the curve, so an increasing knot sequence automatically defines an inscribed polygon.
Write \(f(x)=1-x^4\). The polygon area depends only on the \(x\)-coordinates of the chosen boundary points, so the problem becomes a constrained optimization in one dimension.
The edge from \(P_i\) to \(P_{i+1}\) contributes the area of a trapezoid with heights \(f(x_i)\) and \(f(x_{i+1})\) and width \(x_{i+1}-x_i\). Therefore
$$A(x_1,\dots,x_{n-2})=\sum_{i=0}^{n-2}\frac{f(x_i)+f(x_{i+1})}{2}\,(x_{i+1}-x_i).$$
After substituting \(f(x)=1-x^4\), this becomes
$$A=\sum_{i=0}^{n-2}\frac{2-x_i^4-x_{i+1}^4}{2}\,(x_{i+1}-x_i).$$
This is exactly the quantity accumulated by the numerical solver after the knots have converged.
If \(x_i\) is an interior knot, only the two adjacent segments depend on it. With
$$a=x_{i-1},\qquad t=x_i,\qquad b=x_{i+1},$$
the local contribution is
$$\Phi_i(t)=\frac{2-a^4-t^4}{2}(t-a)+\frac{2-t^4-b^4}{2}(b-t).$$
Differentiating with respect to \(t\) gives
$$\Phi_i'(t)=\frac{b^4-a^4}{2}-2t^3(b-a).$$
At an optimal configuration every interior knot must satisfy \(\Phi_i'(x_i)=0\).
Setting the derivative to zero yields
$$4x_i^3(x_{i+1}-x_{i-1})=x_{i+1}^4-x_{i-1}^4.$$
Solving for \(x_i\) gives the update target
$$x_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
This has a useful geometric interpretation. By the mean value theorem applied to \(u^4\), there exists \(\xi\in(x_{i-1},x_{i+1})\) such that
$$\frac{x_{i+1}^4-x_{i-1}^4}{x_{i+1}-x_{i-1}}=4\xi^3.$$
Hence the cubic-root target is exactly that intermediate point \(\xi\), so it lies between the two neighboring knots.
The exact stationary system is nonlinear, so the implementations solve it numerically. They start from the uniformly spaced mesh
$$x_i=-1+\frac{2i}{n-1}\qquad(0\le i\le n-1)$$
and then sweep through the interior knots with a relaxed fixed-point step
$$x_i\leftarrow x_i+\omega\left(\widehat{x}_i-x_i\right),\qquad \omega=0.5,$$
where
$$\widehat{x}_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
The sweep is Gauss-Seidel style: once one knot is updated, its new value is immediately reused when the next knot is processed. Damping with \(\omega=0.5\) stabilizes the iteration while preserving the same fixed points.
After each full sweep, the implementation records the largest coordinate change. Once that maximum update falls below a tiny tolerance, the knot sequence is treated as converged. The area is then computed from the same trapezoidal sum as in Step 1. The C++ implementation also checks that the knots remain strictly increasing and that the residual
$$4x_i^3(x_{i+1}-x_{i-1})-\left(x_{i+1}^4-x_{i-1}^4\right)$$
is numerically negligible for every interior knot.
For a triangle there is only one interior knot, say \(x_1=t\). The area becomes
$$A(t)=\frac{1-t^4}{2}(t+1)+\frac{1-t^4}{2}(1-t)=1-t^4.$$
This is maximized at \(t=0\), giving the triangle with vertices \((-1,0)\), \((0,1)\), and \((1,0)\). Therefore
$$G(3)=1.$$
This is the first benchmark used to confirm that the numerical method is behaving correctly.
The C++, Python, and Java implementations all follow the same numerical plan. They initialize evenly spaced knots, repeatedly compute the cubic-root target from the two neighboring knots, and move halfway toward that target. The stopping condition is the largest knot displacement in one sweep. After convergence, the implementation sums the segment-wise trapezoid areas and prints the result for \(n=101\).
The only language-level numerical difference is how the real cube root is obtained. This matters on the left half of the interval because the target can be negative, so the implementation must stay on the real line rather than rely on a complex-valued fractional power convention. The C++ implementation also checks the numerical checkpoints \(G(3)=1\) and \(G(5)\approx 1.477309771\).
With \(n\) vertices, one sweep updates \(n-2\) interior knots, so its cost is \(O(n)\). Evaluating the final area also costs \(O(n)\). If \(I\) sweeps are needed for convergence, the total running time is \(O(nI)\), and the memory usage is \(O(n)\) because only the knot coordinates are stored.
Betrachte die Region
$$R=\left\{(x,y):-1\le x\le 1,\ 0\le y\le 1-x^4\right\}.$$
Gesucht ist das flächengrößte \(n\)-Eck in dieser Region für \(n=101\). Die Implementierungen beschreiben das Polygon durch geordnete Randpunkte
$$-1=x_0<x_1<\cdots<x_{n-1}=1,$$
deren Eckpunkte
$$P_i=\left(x_i,\,1-x_i^4\right)$$
sind. Da \(1-x^4\) auf \([-1,1]\) konkav ist, liegt jede Sehne zwischen zwei Randpunkten unter der Kurve. Damit erzeugt jede streng wachsende Knotenfolge automatisch ein einbeschriebenes Polygon.
Wir schreiben \(f(x)=1-x^4\). Die Fläche des Polygons hängt nur von den \(x\)-Koordinaten der gewählten Randpunkte ab, also reduziert sich die Aufgabe auf eine eindimensionale Optimierung unter Ordnungsbedingungen.
Die Kante von \(P_i\) nach \(P_{i+1}\) liefert die Fläche eines Trapezes mit den Höhen \(f(x_i)\) und \(f(x_{i+1})\) und der Breite \(x_{i+1}-x_i\). Daher gilt
$$A(x_1,\dots,x_{n-2})=\sum_{i=0}^{n-2}\frac{f(x_i)+f(x_{i+1})}{2}\,(x_{i+1}-x_i).$$
Nach Einsetzen von \(f(x)=1-x^4\) erhält man
$$A=\sum_{i=0}^{n-2}\frac{2-x_i^4-x_{i+1}^4}{2}\,(x_{i+1}-x_i).$$
Genau diese Summe wird nach der Konvergenz numerisch ausgewertet.
Für einen inneren Knoten \(x_i\) hängen nur die beiden benachbarten Segmente von ihm ab. Mit
$$a=x_{i-1},\qquad t=x_i,\qquad b=x_{i+1}$$
lautet der lokale Beitrag
$$\Phi_i(t)=\frac{2-a^4-t^4}{2}(t-a)+\frac{2-t^4-b^4}{2}(b-t).$$
Die Ableitung nach \(t\) ist
$$\Phi_i'(t)=\frac{b^4-a^4}{2}-2t^3(b-a).$$
In einer optimalen Konfiguration muss für jeden inneren Knoten \(\Phi_i'(x_i)=0\) gelten.
Aus \(\Phi_i'(x_i)=0\) folgt
$$4x_i^3(x_{i+1}-x_{i-1})=x_{i+1}^4-x_{i-1}^4.$$
Damit ergibt sich der Zielwert für den Knoten als
$$x_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
Das hat auch eine geometrische Bedeutung. Nach dem Mittelwertsatz gibt es ein \(\xi\in(x_{i-1},x_{i+1})\) mit
$$\frac{x_{i+1}^4-x_{i-1}^4}{x_{i+1}-x_{i-1}}=4\xi^3.$$
Der Zielwert ist also genau dieser Zwischenpunkt \(\xi\) und liegt deshalb zwischen den beiden Nachbarn.
Das stationäre Gleichungssystem ist nichtlinear. Deshalb lösen die Implementierungen es numerisch. Sie starten mit dem äquidistanten Gitter
$$x_i=-1+\frac{2i}{n-1}\qquad(0\le i\le n-1)$$
und führen dann für alle inneren Knoten den gedämpften Fixpunktschritt
$$x_i\leftarrow x_i+\omega\left(\widehat{x}_i-x_i\right),\qquad \omega=0.5,$$
mit
$$\widehat{x}_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}$$
aus. Der Sweep ist vom Typ Gauss-Seidel: Sobald ein Knoten aktualisiert wurde, wird sein neuer Wert sofort für den nächsten Knoten verwendet. Die Dämpfung mit \(\omega=0.5\) stabilisiert die Rechnung, ohne die Fixpunkte zu verändern.
Nach jedem vollständigen Sweep wird die größte Koordinatenänderung gespeichert. Sobald diese maximale Änderung unter eine sehr kleine Toleranz fällt, gilt die Knotenfolge als konvergiert. Danach wird die Fläche mit derselben Trapezsumme aus Schritt 1 berechnet. Die C++-Implementierung prüft zusätzlich, dass die Knoten streng wachsend bleiben und dass das Residuum
$$4x_i^3(x_{i+1}-x_{i-1})-\left(x_{i+1}^4-x_{i-1}^4\right)$$
für jeden inneren Knoten numerisch vernachlässigbar ist.
Für ein Dreieck gibt es nur einen inneren Knoten \(x_1=t\). Dann ist
$$A(t)=\frac{1-t^4}{2}(t+1)+\frac{1-t^4}{2}(1-t)=1-t^4.$$
Das Maximum liegt bei \(t=0\). Man erhält also das Dreieck mit den Ecken \((-1,0)\), \((0,1)\) und \((1,0)\), und damit
$$G(3)=1.$$
Genau dieser Wert dient als erste numerische Kontrolle der Methode.
Die C++-, Python- und Java-Implementierungen benutzen denselben numerischen Ablauf. Zuerst werden gleichmäßig verteilte Knoten zwischen \(-1\) und \(1\) gesetzt. Danach wird für jeden inneren Knoten aus den beiden Nachbarn der Zielwert per Kubikwurzel berechnet und der aktuelle Knoten halb in diese Richtung verschoben. Abbruchkriterium ist die größte Knotenverschiebung eines kompletten Sweeps. Nach der Konvergenz werden die Trapezflächen segmentweise aufsummiert und für \(n=101\) ausgegeben.
Der einzige spürbare Unterschied zwischen den Sprachen betrifft die reelle Kubikwurzel. Auf der linken Intervallhälfte kann der Zielwert negativ sein, daher muss die Rechnung explizit auf der reellen Achse bleiben und darf sich nicht auf eine komplexwertige Potenzkonvention verlassen. Die C++-Implementierung prüft außerdem die Kontrollwerte \(G(3)=1\) und \(G(5)\approx 1.477309771\).
Bei \(n\) Eckpunkten aktualisiert ein Sweep genau \(n-2\) innere Knoten und kostet daher \(O(n)\). Auch die abschließende Flächenberechnung ist \(O(n)\). Wenn \(I\) Sweeps bis zur Konvergenz nötig sind, beträgt die Gesamtlaufzeit \(O(nI)\), und der Speicherverbrauch ist \(O(n)\), weil nur die Knotenkoordinaten gespeichert werden.
Şu bölgeyi ele alalım:
$$R=\left\{(x,y):-1\le x\le 1,\ 0\le y\le 1-x^4\right\}.$$
Amaç, bu bölge içine çizilebilen en büyük alanlı \(n\)-geni \(n=101\) için bulmaktır. Uygulamalar çokgeni şu sıralı sınır noktalarıyla temsil eder:
$$-1=x_0<x_1<\cdots<x_{n-1}=1,$$
ve köşeler
$$P_i=\left(x_i,\,1-x_i^4\right)$$
şeklindedir. \(1-x^4\) fonksiyonu \([-1,1]\) aralığında konkav olduğu için iki sınır noktası arasındaki her kiriş eğrinin altında kalır. Bu yüzden artan herhangi bir düğüm dizisi otomatik olarak bölgenin içinde kalan bir çokgen verir.
\(f(x)=1-x^4\) yazalım. Çokgenin alanı sadece seçilen sınır noktalarının \(x\)-koordinatlarına bağlıdır; dolayısıyla problem, sıralı bir tek boyutlu optimizasyona indirgenir.
\(P_i\) ile \(P_{i+1}\) arasındaki kenar, yükseklikleri \(f(x_i)\) ve \(f(x_{i+1})\), taban genişliği \(x_{i+1}-x_i\) olan bir trapezin alanını verir. Bu nedenle
$$A(x_1,\dots,x_{n-2})=\sum_{i=0}^{n-2}\frac{f(x_i)+f(x_{i+1})}{2}\,(x_{i+1}-x_i)$$
olur. \(f(x)=1-x^4\) yerine yazınca
$$A=\sum_{i=0}^{n-2}\frac{2-x_i^4-x_{i+1}^4}{2}\,(x_{i+1}-x_i)$$
elde edilir. Yakınsama sağlandıktan sonra programın topladığı nicelik tam olarak budur.
Bir iç düğüm \(x_i\) için yalnızca iki komşu kenar bu değişkene bağlıdır. Şöyle yazalım:
$$a=x_{i-1},\qquad t=x_i,\qquad b=x_{i+1}.$$
Bu durumda yerel katkı
$$\Phi_i(t)=\frac{2-a^4-t^4}{2}(t-a)+\frac{2-t^4-b^4}{2}(b-t)$$
olur. \(t\)'ye göre türev alırsak
$$\Phi_i'(t)=\frac{b^4-a^4}{2}-2t^3(b-a)$$
sonucuna ulaşırız. En iyi konumda her iç düğüm için \(\Phi_i'(x_i)=0\) olmalıdır.
Türevi sıfıra eşitleyince
$$4x_i^3(x_{i+1}-x_{i-1})=x_{i+1}^4-x_{i-1}^4$$
elde edilir. Buradan güncelleme hedefi
$$x_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}$$
şeklindedir. Bunun güzel bir geometrik yorumu vardır. \(u^4\) fonksiyonuna ortalama değer teoremi uygularsak \((x_{i-1},x_{i+1})\) içinde bir \(\xi\) vardır ve
$$\frac{x_{i+1}^4-x_{i-1}^4}{x_{i+1}-x_{i-1}}=4\xi^3$$
olur. Yani küpkök ifadesi tam olarak bu ara noktayı verir; dolayısıyla hedef değer iki komşu düğümün arasındadır.
Durağanlık sistemi doğrusal değildir; bu yüzden uygulamalar onu sayısal olarak çözer. Başlangıç olarak eşit aralıklı ağ kullanılır:
$$x_i=-1+\frac{2i}{n-1}\qquad(0\le i\le n-1).$$
Ardından her iç düğüm için sönümlü sabit nokta adımı uygulanır:
$$x_i\leftarrow x_i+\omega\left(\widehat{x}_i-x_i\right),\qquad \omega=0.5,$$
burada
$$\widehat{x}_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
Tarama Gauss-Seidel tipindedir; bir düğüm güncellenince yeni değer hemen sonraki düğümün hesabında kullanılır. \(\omega=0.5\) sönüm katsayısı sabit noktaları değiştirmeden yakınsamayı daha kararlı hale getirir.
Her tam turdan sonra en büyük koordinat değişimi kaydedilir. Bu maksimum güncelleme çok küçük bir toleransın altına düştüğünde düğüm dizisinin yakınsadığı kabul edilir. Son alan, Adım 1'deki aynı trapez toplamıyla bulunur. C++ uygulaması ayrıca düğümlerin sıkı biçimde artan kaldığını ve
$$4x_i^3(x_{i+1}-x_{i-1})-\left(x_{i+1}^4-x_{i-1}^4\right)$$
kalıntısının her iç düğüm için ihmal edilebilir büyüklükte olduğunu kontrol eder.
Üçgen durumunda yalnızca bir iç düğüm vardır; \(x_1=t\) diyelim. Alan
$$A(t)=\frac{1-t^4}{2}(t+1)+\frac{1-t^4}{2}(1-t)=1-t^4$$
olur. Maksimum \(t=0\)'da elde edilir. Böylece köşeleri \((-1,0)\), \((0,1)\) ve \((1,0)\) olan üçgen bulunur ve
$$G(3)=1$$
sonucuna ulaşılır. Bu değer, sayısal yöntemin ilk kontrol noktasıdır.
C++, Python ve Java uygulamaları aynı sayısal planı izler. Önce \(-1\) ile \(1\) arasında eşit aralıklı düğümler kuruluyor. Sonra her iç düğüm için iki komşudan küpkök hedefi hesaplanıyor ve mevcut konum o hedefe doğru yarım adım kaydırılıyor. Durdurma ölçütü, bir tur içindeki en büyük düğüm yer değiştirmesi. Yakınsamadan sonra segment bazında trapez alanları toplanıyor ve \(n=101\) sonucu yazdırılıyor.
Diller arasındaki temel sayısal fark, reel küpkök hesabının nasıl yapıldığıdır. Aralığın sol yarısında hedef değer negatif olabileceği için uygulamanın reel eksende kalması gerekir; karmaşık değerli üs alma geleneğine güvenmek doğru olmaz. C++ uygulaması ayrıca \(G(3)=1\) ve \(G(5)\approx 1.477309771\) denetimlerini de yapar.
\(n\) köşeli durumda bir tur tam olarak \(n-2\) iç düğümü günceller; bu yüzden maliyeti \(O(n)\)'dir. Son alan hesabı da \(O(n)\) zaman alır. Yakınsamak için \(I\) tur gerekirse toplam süre \(O(nI)\), bellek kullanımı ise yalnızca düğüm koordinatları saklandığından \(O(n)\) olur.
Consideremos la región
$$R=\left\{(x,y):-1\le x\le 1,\ 0\le y\le 1-x^4\right\}.$$
Buscamos el \(n\)-gono de área máxima contenido en esa región para \(n=101\). Las implementaciones representan el polígono mediante puntos de borde ordenados
$$-1=x_0<x_1<\cdots<x_{n-1}=1,$$
con vértices
$$P_i=\left(x_i,\,1-x_i^4\right).$$
Como \(1-x^4\) es una función cóncava en \([-1,1]\), cualquier cuerda entre dos puntos del borde queda por debajo de la curva. Por eso, una sucesión estrictamente creciente de nodos ya define un polígono inscrito dentro de la región.
Escribimos \(f(x)=1-x^4\). El área del polígono depende solo de las coordenadas \(x\) de los puntos elegidos en el borde, así que el problema se reduce a una optimización unidimensional con restricciones de orden.
El lado que une \(P_i\) con \(P_{i+1}\) aporta el área de un trapecio con alturas \(f(x_i)\) y \(f(x_{i+1})\) y base \(x_{i+1}-x_i\). Por tanto,
$$A(x_1,\dots,x_{n-2})=\sum_{i=0}^{n-2}\frac{f(x_i)+f(x_{i+1})}{2}\,(x_{i+1}-x_i).$$
Sustituyendo \(f(x)=1-x^4\), obtenemos
$$A=\sum_{i=0}^{n-2}\frac{2-x_i^4-x_{i+1}^4}{2}\,(x_{i+1}-x_i).$$
Esa es exactamente la cantidad que se acumula al final de la iteración numérica.
Si \(x_i\) es interior, solo los dos segmentos adyacentes dependen de él. Definimos
$$a=x_{i-1},\qquad t=x_i,\qquad b=x_{i+1}.$$
La contribución local es entonces
$$\Phi_i(t)=\frac{2-a^4-t^4}{2}(t-a)+\frac{2-t^4-b^4}{2}(b-t).$$
Derivando respecto de \(t\) se obtiene
$$\Phi_i'(t)=\frac{b^4-a^4}{2}-2t^3(b-a).$$
En una configuración óptima, cada nodo interior debe cumplir \(\Phi_i'(x_i)=0\).
Al imponer \(\Phi_i'(x_i)=0\) resulta
$$4x_i^3(x_{i+1}-x_{i-1})=x_{i+1}^4-x_{i-1}^4.$$
Por lo tanto, el valor objetivo para actualizar el nodo es
$$x_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
Esto también tiene una interpretación geométrica. Aplicando el teorema del valor medio a \(u^4\), existe \(\xi\in(x_{i-1},x_{i+1})\) tal que
$$\frac{x_{i+1}^4-x_{i-1}^4}{x_{i+1}-x_{i-1}}=4\xi^3.$$
Así, la expresión con raíz cúbica es exactamente ese punto intermedio \(\xi\), de modo que siempre queda entre los vecinos.
El sistema estacionario es no lineal, así que las implementaciones lo resuelven numéricamente. Se parte de la malla uniforme
$$x_i=-1+\frac{2i}{n-1}\qquad(0\le i\le n-1)$$
y luego se hace un barrido por los nodos interiores con el paso relajado
$$x_i\leftarrow x_i+\omega\left(\widehat{x}_i-x_i\right),\qquad \omega=0.5,$$
donde
$$\widehat{x}_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
El barrido es de tipo Gauss-Seidel: cuando un nodo ya fue actualizado, su valor nuevo se reutiliza inmediatamente para el siguiente. El factor \(\omega=0.5\) amortigua la dinámica y hace la convergencia más estable.
Después de cada barrido completo se guarda el mayor cambio de coordenada. Cuando ese desplazamiento máximo cae por debajo de una tolerancia muy pequeña, la secuencia de nodos se considera convergida. Entonces se calcula el área final usando la misma suma trapezoidal del Paso 1. La implementación en C++ además verifica que los nodos sigan en orden estricto y que el residuo
$$4x_i^3(x_{i+1}-x_{i-1})-\left(x_{i+1}^4-x_{i-1}^4\right)$$
sea numéricamente despreciable para cada nodo interior.
Para un triángulo solo existe un nodo interior, \(x_1=t\). El área vale
$$A(t)=\frac{1-t^4}{2}(t+1)+\frac{1-t^4}{2}(1-t)=1-t^4.$$
Su máximo ocurre en \(t=0\). Así se obtiene el triángulo con vértices \((-1,0)\), \((0,1)\) y \((1,0)\), y por tanto
$$G(3)=1.$$
Ese es el primer punto de control numérico usado por el método.
Las implementaciones en C++, Python y Java siguen el mismo esquema numérico. Primero colocan nodos uniformemente espaciados entre \(-1\) y \(1\). Después, en cada barrido, calculan para cada nodo interior el objetivo dado por la raíz cúbica de sus dos vecinos y lo mueven la mitad del camino hacia ese objetivo. El criterio de parada es el mayor desplazamiento de un nodo durante un barrido completo. Una vez alcanzada la convergencia, la implementación suma las áreas trapezoidales de todos los segmentos y produce el resultado para \(n=101\).
La única diferencia numérica visible entre lenguajes es la forma de obtener la raíz cúbica real. En la mitad izquierda del intervalo el objetivo puede ser negativo, así que la implementación debe mantenerse en los números reales en lugar de depender de una potencia fraccionaria con posibles convenciones complejas. La versión en C++ también comprueba los valores de referencia \(G(3)=1\) y \(G(5)\approx 1.477309771\).
Con \(n\) vértices, un barrido actualiza \(n-2\) nodos interiores y cuesta \(O(n)\). El cálculo final del área también cuesta \(O(n)\). Si hacen falta \(I\) barridos para converger, el tiempo total es \(O(nI)\) y la memoria usada es \(O(n)\), porque solo se almacena la lista de coordenadas.
考虑区域
$$R=\left\{(x,y):-1\le x\le 1,\ 0\le y\le 1-x^4\right\}.$$
题目要求在这个区域内构造面积最大的 \(n\) 边形，这里最终需要的是 \(n=101\) 的结果。实现采用一组按顺序排列的边界点
$$-1=x_0<x_1<\cdots<x_{n-1}=1,$$
并把顶点写成
$$P_i=\left(x_i,\,1-x_i^4\right).$$
由于函数 \(1-x^4\) 在 \([-1,1]\) 上是凹函数，任意两点之间的弦都落在曲线下方，所以只要节点严格递增，由这些边界点连成的折线就天然位于区域内部。这正是数值算法能够只优化 \(x\) 坐标的原因。
记 \(f(x)=1-x^4\)。这样一来，多边形面积只依赖于所选边界点的 \(x\) 坐标，原问题就变成了一个带顺序约束的一维优化问题。
相邻两个顶点 \(P_i\) 和 \(P_{i+1}\) 之间的边，对应一个高分别为 \(f(x_i)\) 和 \(f(x_{i+1})\)、宽为 \(x_{i+1}-x_i\) 的梯形。因此总面积为
$$A(x_1,\dots,x_{n-2})=\sum_{i=0}^{n-2}\frac{f(x_i)+f(x_{i+1})}{2}\,(x_{i+1}-x_i).$$
代入 \(f(x)=1-x^4\) 后得到
$$A=\sum_{i=0}^{n-2}\frac{2-x_i^4-x_{i+1}^4}{2}\,(x_{i+1}-x_i).$$
这正是实现最终累加的面积表达式。也可以把它理解为折线下方区域的分段梯形面积之和。
如果 \(x_i\) 是内部节点，那么只有它左右两段会随之改变。设
$$a=x_{i-1},\qquad t=x_i,\qquad b=x_{i+1}.$$
固定邻点 \(a\) 和 \(b\) 后，与 \(t\) 有关的局部面积就是
$$\Phi_i(t)=\frac{2-a^4-t^4}{2}(t-a)+\frac{2-t^4-b^4}{2}(b-t).$$
对 \(t\) 求导可得
$$\Phi_i'(t)=\frac{b^4-a^4}{2}-2t^3(b-a).$$
在最优配置中，每个内部节点都必须满足 \(\Phi_i'(x_i)=0\)。这一步把原来的整体优化问题拆成了“每个点在固定邻居下应该停在哪里”的局部条件。
令导数为零，就得到
$$4x_i^3(x_{i+1}-x_{i-1})=x_{i+1}^4-x_{i-1}^4.$$
因此内部节点的目标位置满足
$$x_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
这个公式还有一个很直观的解释。对函数 \(u^4\) 使用中值定理，可知存在某个 \(\xi\in(x_{i-1},x_{i+1})\) 使得
$$\frac{x_{i+1}^4-x_{i-1}^4}{x_{i+1}-x_{i-1}}=4\xi^3.$$
于是上面的立方根目标值正好就是这个中间点 \(\xi\)。换句话说，新位置一定落在左右邻点之间，不会无端跳出局部区间。
完整的驻点系统是非线性的，不能直接一步解出所有内部节点。实现采用数值迭代：先从等距网格出发，取
$$x_i=-1+\frac{2i}{n-1}\qquad(0\le i\le n-1),$$
然后对每个内部节点做阻尼固定点更新
$$x_i\leftarrow x_i+\omega\left(\widehat{x}_i-x_i\right),\qquad \omega=0.5,$$
其中
$$\widehat{x}_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
这里的扫描方式是 Gauss-Seidel 风格，也就是某个节点一旦更新，后续节点马上使用它的新值。这样的写法比“整轮算完再一起替换”更贴近实现，也更容易稳定收敛。阻尼系数 \(\omega=0.5\) 不会改变真正的固定点，但会抑制震荡。
每完成一轮扫描，实现都会记录本轮中最大的坐标变化量。如果这个最大改变量已经小到低于给定阈值，就认为节点已经收敛。随后再使用步骤 1 的梯形公式计算最终面积。C++ 实现还额外检查两件事：一是节点仍然保持严格递增，二是每个内部节点的残差
$$4x_i^3(x_{i+1}-x_{i-1})-\left(x_{i+1}^4-x_{i-1}^4\right)$$
在数值上足够接近零，从而确认驻点条件确实被满足。
当 \(n=3\) 时，只有一个内部节点，记作 \(x_1=t\)。此时面积可以直接化简为
$$A(t)=\frac{1-t^4}{2}(t+1)+\frac{1-t^4}{2}(1-t)=1-t^4.$$
显然它在 \(t=0\) 处取得最大值，于是最优三角形的三个顶点是 \((-1,0)\)、\((0,1)\)、\((1,0)\)，对应
$$G(3)=1.$$
这个结果正是实现中用来校验算法的第一个基准值。
C++、Python 和 Java 实现遵循同一个数值流程。它们先把节点均匀放在 \([-1,1]\) 上，然后反复扫描所有内部节点：根据左右邻点计算立方根目标值，再把当前节点向该目标移动一半。停止条件是一整轮扫描中出现的最大位移足够小。收敛后，程序按段累加梯形面积，并输出 \(n=101\) 的结果。
三个语言版本在算法上没有本质差别，主要区别只在浮点细节，特别是“实数立方根”的处理。因为区间左半边的目标值可能为负，所以实现必须明确使用实数意义下的立方根，而不能把分数次幂交给可能走向复数分支的约定。C++ 版本还会检查两个数值基准：\(G(3)=1\) 与 \(G(5)\approx 1.477309771\)。
若共有 \(n\) 个顶点，则一轮扫描更新 \(n-2\) 个内部节点，时间是 \(O(n)\)。最后一次面积求和同样是 \(O(n)\)。如果总共需要 \(I\) 轮迭代才能收敛，那么总时间复杂度就是 \(O(nI)\)，空间复杂度是 \(O(n)\)，因为程序只保存节点坐标本身。
Рассмотрим область
$$R=\left\{(x,y):-1\le x\le 1,\ 0\le y\le 1-x^4\right\}.$$
Нужно найти вписанный в эту область \(n\)-угольник максимальной площади при \(n=101\). В реализации он задается упорядоченными граничными точками
$$-1=x_0<x_1<\cdots<x_{n-1}=1,$$
с вершинами
$$P_i=\left(x_i,\,1-x_i^4\right).$$
Функция \(1-x^4\) в интервале \([-1,1]\) вогнута, поэтому каждая хорда между двумя точками графика лежит ниже самой кривой. Значит, любая строго возрастающая последовательность узлов автоматически задает многоугольник, целиком лежащий в нужной области.
Обозначим \(f(x)=1-x^4\). Тогда площадь многоугольника зависит только от выбранных \(x\)-координат на границе, и задача сводится к одномерной оптимизации с условием порядка.
Ребро между \(P_i\) и \(P_{i+1}\) дает площадь трапеции с высотами \(f(x_i)\) и \(f(x_{i+1})\) и шириной \(x_{i+1}-x_i\). Поэтому
$$A(x_1,\dots,x_{n-2})=\sum_{i=0}^{n-2}\frac{f(x_i)+f(x_{i+1})}{2}\,(x_{i+1}-x_i).$$
После подстановки \(f(x)=1-x^4\) получаем
$$A=\sum_{i=0}^{n-2}\frac{2-x_i^4-x_{i+1}^4}{2}\,(x_{i+1}-x_i).$$
Именно эта сумма вычисляется программой после того, как узлы сошлись.
Если \(x_i\) внутренний, то от него зависят только два соседних отрезка. Обозначим
$$a=x_{i-1},\qquad t=x_i,\qquad b=x_{i+1}.$$
Тогда локальный вклад равен
$$\Phi_i(t)=\frac{2-a^4-t^4}{2}(t-a)+\frac{2-t^4-b^4}{2}(b-t).$$
Производная по \(t\) имеет вид
$$\Phi_i'(t)=\frac{b^4-a^4}{2}-2t^3(b-a).$$
В оптимальной конфигурации для каждого внутреннего узла должно выполняться \(\Phi_i'(x_i)=0\).
Из условия \(\Phi_i'(x_i)=0\) следует
$$4x_i^3(x_{i+1}-x_{i-1})=x_{i+1}^4-x_{i-1}^4.$$
Отсюда целевое положение узла выражается как
$$x_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
У этого выражения есть полезная геометрическая интерпретация. По теореме о среднем значении для функции \(u^4\) существует \(\xi\in(x_{i-1},x_{i+1})\) такое, что
$$\frac{x_{i+1}^4-x_{i-1}^4}{x_{i+1}-x_{i-1}}=4\xi^3.$$
Следовательно, целевое значение по формуле с кубическим корнем и есть этот промежуточный узел \(\xi\), то есть оно всегда лежит между соседями.
Система стационарности нелинейна, поэтому реализации решают ее численно. Стартовая сетка берется равномерной:
$$x_i=-1+\frac{2i}{n-1}\qquad(0\le i\le n-1).$$
После этого внутренние узлы обновляются по демпфированному шагу фиксированной точки
$$x_i\leftarrow x_i+\omega\left(\widehat{x}_i-x_i\right),\qquad \omega=0.5,$$
где
$$\widehat{x}_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
Проход выполняется в стиле Гаусса-Зейделя: как только узел обновлен, его новое значение сразу используется при обработке следующего. Демпфирование с \(\omega=0.5\) не меняет фиксированные точки, но заметно улучшает устойчивость сходимости.
После каждого полного прохода сохраняется максимальное изменение координаты. Когда это максимальное смещение становится меньше очень малого порога, последовательность узлов считается сошедшейся. Затем площадь вычисляется той же трапецеидальной суммой из шага 1. В версии на C++ дополнительно проверяется строгая монотонность узлов и малость остатка
$$4x_i^3(x_{i+1}-x_{i-1})-\left(x_{i+1}^4-x_{i-1}^4\right)$$
для каждого внутреннего узла.
Для треугольника есть только один внутренний узел, пусть \(x_1=t\). Тогда
$$A(t)=\frac{1-t^4}{2}(t+1)+\frac{1-t^4}{2}(1-t)=1-t^4.$$
Максимум достигается при \(t=0\). Получается треугольник с вершинами \((-1,0)\), \((0,1)\) и \((1,0)\), а значит
$$G(3)=1.$$
Это первое контрольное значение, которым подтверждается корректность численного метода.
Реализации на C++, Python и Java используют один и тот же численный алгоритм. Сначала создаются равномерно расположенные узлы от \(-1\) до \(1\). Затем на каждом проходе для каждого внутреннего узла вычисляется целевая точка по формуле с кубическим корнем, и текущий узел сдвигается к ней на половину расстояния. Критерий остановки — максимальное смещение узла за один полный проход. После сходимости программа суммирует площади всех трапеций и выводит результат для \(n=101\).
Отличия между языками касаются только численных деталей, прежде всего вычисления вещественного кубического корня. В левой половине интервала целевое значение может быть отрицательным, поэтому нужно явно оставаться в вещественной арифметике, а не полагаться на соглашение о дробной степени, которое может уходить в комплексную область. Версия на C++ также проверяет контрольные значения \(G(3)=1\) и \(G(5)\approx 1.477309771\).
При \(n\) вершинах один проход обновляет \(n-2\) внутренних узла, значит его стоимость равна \(O(n)\). Финальное вычисление площади также занимает \(O(n)\). Если для сходимости нужно \(I\) проходов, то полное время работы равно \(O(nI)\), а память — \(O(n)\), потому что хранится только массив координат узлов.
لننظر إلى المنطقة
$$R=\left\{(x,y):-1\le x\le 1,\ 0\le y\le 1-x^4\right\}.$$
المطلوب هو إيجاد المضلع ذي المساحة العظمى داخل هذه المنطقة عندما \(n=101\). تمثل التطبيقات هذا المضلع عبر نقاط حدية مرتبة
$$-1=x_0<x_1<\cdots<x_{n-1}=1,$$
بحيث تكون الرؤوس
$$P_i=\left(x_i,\,1-x_i^4\right).$$
وبما أن الدالة \(1-x^4\) مقعرة على الفترة \([-1,1]\)، فإن كل وتر يصل بين نقطتين من المنحنى يقع تحت المنحنى نفسه. لذلك فإن أي ترتيب متزايد للعقد يعطي مباشرة مضلعًا منقوشًا بالكامل داخل المنطقة.
لنكتب \(f(x)=1-x^4\). عندئذ تعتمد مساحة المضلع فقط على إحداثيات \(x\) للنقاط المختارة على الحد، وبالتالي تتحول المسألة إلى تحسين أحادي البعد مع شرط ترتيب العقد.
الضلع الواصل بين \(P_i\) و\(P_{i+1}\) يعطي مساحة شبه منحرف ارتفاعاه \(f(x_i)\) و\(f(x_{i+1})\) وعرضه \(x_{i+1}-x_i\). لذلك
$$A(x_1,\dots,x_{n-2})=\sum_{i=0}^{n-2}\frac{f(x_i)+f(x_{i+1})}{2}\,(x_{i+1}-x_i).$$
وبالتعويض عن \(f(x)=1-x^4\) نحصل على
$$A=\sum_{i=0}^{n-2}\frac{2-x_i^4-x_{i+1}^4}{2}\,(x_{i+1}-x_i).$$
وهذه هي بالضبط الكمية التي تجمعها الخوارزمية بعد انتهاء التكرار العددي.
إذا كانت \(x_i\) عقدة داخلية، فإن المقطعين المجاورين فقط يعتمدان عليها. نضع
$$a=x_{i-1},\qquad t=x_i,\qquad b=x_{i+1}.$$
وعندها تكون المساهمة المحلية
$$\Phi_i(t)=\frac{2-a^4-t^4}{2}(t-a)+\frac{2-t^4-b^4}{2}(b-t).$$
وباستخراج المشتقة بالنسبة إلى \(t\) نحصل على
$$\Phi_i'(t)=\frac{b^4-a^4}{2}-2t^3(b-a).$$
في الوضع الأمثل يجب أن يحقق كل موضع داخلي الشرط \(\Phi_i'(x_i)=0\).
من مساواة المشتقة بالصفر ينتج
$$4x_i^3(x_{i+1}-x_{i-1})=x_{i+1}^4-x_{i-1}^4.$$
ومن ثم يكون موضع التحديث الهدف
$$x_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
لهذا التعبير تفسير هندسي مفيد. فبتطبيق مبرهنة القيمة المتوسطة على \(u^4\) يوجد عدد \(\xi\) بين \(x_{i-1}\) و\(x_{i+1}\) بحيث
$$\frac{x_{i+1}^4-x_{i-1}^4}{x_{i+1}-x_{i-1}}=4\xi^3.$$
إذن قيمة الجذر التكعيبي هي هذا الموضع الوسيط نفسه، ولذلك تبقى دائمًا بين الجارتين.
منظومة السكون غير خطية، لذلك تعالجها التطبيقات عدديًا. تبدأ الشبكة من التوزيع المنتظم
$$x_i=-1+\frac{2i}{n-1}\qquad(0\le i\le n-1),$$
ثم يجرى على كل عقدة داخلية تحديث مخمّد من نوع النقطة الثابتة:
$$x_i\leftarrow x_i+\omega\left(\widehat{x}_i-x_i\right),\qquad \omega=0.5,$$
حيث
$$\widehat{x}_i=\sqrt[3]{\frac{x_{i+1}^4-x_{i-1}^4}{4(x_{i+1}-x_{i-1})}}.$$
ويمر المسح بطريقة تشبه Gauss-Seidel: ما إن تُحدَّث عقدة حتى يستعمل مقدارها الجديد مباشرة في العقدة التالية. هذا يجعل الوصف مطابقًا لما يحدث فعلاً في التنفيذ، كما أن التخميد \(\omega=0.5\) يساعد على الاستقرار دون تغيير نقاط التثبيت الحقيقية.
بعد كل دورة كاملة تسجل الخوارزمية أكبر إزاحة حدثت لأي عقدة. وعندما تصبح هذه الإزاحة القصوى أصغر من حد صغير جدًا تعتبر العقد قد تقاربت. بعد ذلك تحسب المساحة النهائية باستعمال نفس مجموع أشباه المنحرفات الوارد في الخطوة 1. كما يتحقق تنفيذ C++ أيضًا من بقاء العقد مرتبة ترتيبًا تصاعديًا صارمًا ومن أن الباقي
$$4x_i^3(x_{i+1}-x_{i-1})-\left(x_{i+1}^4-x_{i-1}^4\right)$$
ضئيل عدديًا عند كل عقدة داخلية.
في حالة المثلث توجد عقدة داخلية واحدة فقط، ولنسمها \(x_1=t\). تصبح المساحة
$$A(t)=\frac{1-t^4}{2}(t+1)+\frac{1-t^4}{2}(1-t)=1-t^4.$$
ومن الواضح أن القيمة العظمى تتحقق عند \(t=0\). وبذلك نحصل على مثلث رؤوسه \((-1,0)\) و\((0,1)\) و\((1,0)\)، وبالتالي
$$G(3)=1.$$
وهذه هي أول قيمة مرجعية تستخدمها الطريقة العددية للتحقق من صحة السلوك.
تتبع تطبيقات C++ وPython وJava الخطة العددية نفسها. تبدأ أولًا بعقد موزعة بانتظام بين \(-1\) و\(1\)، ثم تكرر مسح العقد الداخلية: تحسب لكل عقدة القيمة الهدف من الجذر التكعيبي المعتمد على الجارتين، ثم تحرك العقدة نصف المسافة نحو ذلك الهدف. معيار التوقف هو أكبر إزاحة لأي عقدة خلال دورة كاملة. وبعد التقارب تجمع الشيفرة مساحات أشباه المنحرفات على جميع المقاطع وتطبع النتيجة عندما \(n=101\).
الفرق العددي الأساسي بين اللغات يتعلق بكيفية الحصول على الجذر التكعيبي الحقيقي. ففي النصف الأيسر من الفترة قد تكون القيمة الهدف سالبة، ولهذا يجب أن يبقى التنفيذ ضمن الأعداد الحقيقية بدل الاعتماد على أس كسري قد يتبع اصطلاحًا مركبًا. كما يتحقق تنفيذ C++ من القيمتين المرجعيتين \(G(3)=1\) و\(G(5)\approx 1.477309771\).
إذا كان للمضلع \(n\) رأسًا، فإن كل دورة تحدث \(n-2\) عقدًا داخلية، ولذلك تكلفتها \(O(n)\). كما أن حساب المساحة النهائي يكلف \(O(n)\) أيضًا. وإذا احتاجت الخوارزمية إلى \(I\) دورات حتى التقارب، فزمن التنفيذ الكلي يساوي \(O(nI)\)، أما الذاكرة فهي \(O(n)\) لأن ما يخزن فعليًا هو إحداثيات العقد فقط.