Codex @codex  0

The Newton root-finding iteration for this quadratic polynomial isAt $x_0=1$, it gives $x_1=1/(1-\epsilon )$. Its geometric series expansion is $1+\epsilon +{\epsilon }^2+{\epsilon }^3+O({\epsilon }^4)$. Subtracting the expansion of the polynomial root yields

For this polynomial, $f^{\prime }(x)=2x$, so the specified Newton root-finding iteration simplifies toStarting at one gives $x_1=(1+2)/2=3/2$, followed by $x_2=(3/2+4/3)/2=17/12$. Consequently

Setting the tangent line approximation equal to zero gives the Newton root-finding iterationThe step requires a nonzero derivative at the starting point.

Here $f(1)=-1$ and $f^{\prime }(x)=1+1/x$, so $f^{\prime }(1)=2$. The Newton root-finding iteration gives

The Newton root-finding iteration replaces the graph by its tangent line at $x_0$ and uses that line's zero:Comparing with the printed reciprocal-ratio form givesThis step requires $f^{\prime }(x_0)\ne 0$. If $f(x_0)=0$, the iteration has already reached a zero of a function and the printed reciprocal-ratio expression need not be evaluated.

With $f(x,y)=-x{y}^2-y^5$, write $t=x_{n+1}=x_n+h$ and $z=y_{n+1}$. The Backward Euler method requiresor the monic quintic polynomial equationConstruct its $5\times 5$ companion matrixIts characteristic polynomial is $\det (zI-C_n)=p(z)$. Thus the polynomial roots needed for this update are exactly the eigenvalues of $C_n$.

At each step, assemble $C_n$, compute its eigenvalues, for example with the QR algorithm, and choose its unique positive real eigenvalue as $y_{n+1}$. To justify this selection, letIf $y_n>0$, then $F(0)=-y_n<0$, $F(y_n)=h{y}_n^5+ht{y}_n^2>0$, andThe intermediate value theorem and strict monotonicity prove there is exactly one positive polynomial root, located in $(0,y_n)$. Starting at $y_0=1$ therefore makes every update well defined, positive and decreasing. In numerical arithmetic, select the nearly real eigenvalue in this interval and check the polynomial residual $|F(z)|$; a final Newton root-finding iteration can refine it. This reduces each update to the requested eigenvalue problem.

The multinomial likelihood is a parameter-independent factor times ${\prod }_i{\pi }_i^{n_i}$. Maximize its logarithm subject to $\sum {\pi }_i=1$: the multiplier equations give $n_i/{\pi }_i=c$, and summation makes $c=n$. Thus ${\hat{\pi }}_i=n_i/n$. Positivity of all counts makes this the unique interior maximum by strict concavity.

The likelihood ratio compares the fitted null likelihood with this saturated likelihood. Taking minus twice its logarithm gives $\Lambda (\hat{\theta })=2{\sum }_i{n}_i\log [n_i/(n{\pi }_i(\hat{\theta }))]$. Under regularity and large expected counts, compare it to ${\chi }_{k-2}^2$ for one fitted parameter: the saturated probabilities have $k-1$ free coordinates and the null has one. If the parameter is fixed at ${\theta }_0$, use $\Lambda ({\theta }_0)$ and ${\chi }_{k-1}^2$. Reject for a value above the chosen upper quantile.

For the ungrouped logarithmic-series observations write $n=1188$ and $S={\sum }_r{X}_r=6968$. The log likelihood isSetting its derivative to zero givesBisection of this monotone mean equation, or Newton's method with a valid bracket, obtains ${\hat{\theta }}_{\mathrm{full}}\approx 0.9442280$.

The supplied table instead uses ten grouped cells, with the last probability ${\pi }_{\ge 10}(\theta )=1-{\sum }_{i=1}^9{\pi }_i(\theta )$. Its likelihood is determined by the cell counts and is not the ungrouped likelihood just differentiated. From its listed values, the minimum deviance occurs near $\boxed{{\hat{\theta }}_{\mathrm{grouped}}\approx 0.93}$; direct minimization of this grouped deviance gives about $0.9333714$. The supplied two forms of the estimate therefore concern different likelihoods. They must not be identified: the full-data score equation gives about $0.94423$, while the grouped table points near $0.93$. The following requested tests use the table's grouped likelihood, with ten cells. The source values and totals are preserved unchanged in TeX.

Let $e_k=x_k-x_{\ast }$, with $f^{\prime }(x_{\ast })=0$, $f^{\prime \prime }(x_{\ast })\ne 0$. Taylor expansion givesDivision in the Newton update yieldsThus convergence is generically quadratic when that coefficient is nonzero. With a locally Lipschitz second derivative and nonzero $f^{\prime \prime }(x_{\ast })$, the weaker estimate $|e_{k+1}|\le C|e_k{|}^2$ also proves local quadratic convergence.

“Quadratic at best” is false as a universal upper bound. If the displayed coefficient vanishes, the order can be higher. For example $f(x)=x^2/2+x^4/4$ has a minimum at zero, and its Newton optimization update is $x_{k+1}=2x_k^3/(1+3x_k^2)$, which has cubic convergence. For a nondegenerate quadratic objective the method reaches the stationary point in one step. The expansion proves the standard generic quadratic statement while retaining and correcting the source's stronger wording explicitly.

On $I=[1,7/5]$, $f^{\prime }<0$ and $f^{\prime \prime }<0$, since $x^2<2$. Hence $|f^{\prime }|$ increases and has minimum $|f^{\prime }(1)|=14$. Alsowith equality at $x=1$. Therefore

There is a unique root $r$ in $I$: $f(1)=2>0$, $f(7/5)=-5.678464<0$, and the function is strictly decreasing. Moreover $f(6/5)=-1.382016<0$, so $r<6/5=x_0$.

It remains to justify that the iteration stays where the error estimate applies. Because $f$ is a concave function, its graph lies below each tangent line. At any $x\in [r,6/5]$, the tangent has nonpositive value $f(x)$ at $x$, negative slope, and nonnegative value at $r$. Its zero $N(x)=x-f(x)/f^{\prime }(x)$ therefore satisfiesBy mathematical induction, the Newton root-finding iteration stays in $[r,6/5]$ and decreases to some limit $L\ge r$. Continuity in $x_{k+1}-x_k=-f(x_k)/f^{\prime }(x_k)$ implies $f(L)=0$, so uniqueness gives $L=r$.

Now the supplied error bound applies at every step:This proves at least quadratic convergence, with an invariant interval and a nonvanishing derivative explicitly established.

The Newton root-finding iteration isIt is defined when $x_k\notin \{0,\pm \sqrt{10/3}\}$. Finding an exact zero of a function is a stopping condition, rather than a reason to continue dividing.

For the vector equation, the Jacobian matrix isWrite the updated coordinates as $(X,Y)$. The second equation of the multivariable Newton iteration gives $X-Y=0$. Substituting $X=Y$ into its first linearized equation givesHence $h(x,y)=6x^5-20y^3$, and, whenever $h\ne 0$,

Starting from $(0,1)$ gives $(x_1,y_1)=(21/20,21/20)$. Every subsequent iterate remains on the diagonal, where this is exactly the scalar Newton root-finding iteration from (b). The value $f(21/20)>0$, so $21/20<r$.

For $1\le x<r$, concavity again puts the tangent's zero at or above $r$. Alsoso $r\le N(21/20)\le N(1)=8/7<6/5$. After one scalar step the sequence therefore enters the invariant interval proved in (b). It converges to $(r,r)$ at least quadratically. If the vector error is measured in the Euclidean norm, then $\Vert (x_k,y_k)-(r,r)\Vert =\sqrt{2}|x_k-r|$, so the scalar quadratic estimate also gives a quadratic vector estimate. The initial off-diagonal step causes no difficulty because its Jacobian matrix is invertible and lands exactly on the diagonal.

Apply the mean value theorem, the first-order case of Taylor's theorem, to $f^{\prime }$ between $0$ and $x>1$. It yieldsAlso $f(3/2)\ge -5+9/2+9/4=7/4>0$, so the initial point is to the right of the root $x^{\ast }$. For an increasing strictly convex function, its tangent at a point to the right of a root meets the axis between that root and the point. Hence the exact Newton root-finding iteration remains in $[x^{\ast },3/2]$ and decreases towards $x^{\ast }$.

On every relevant interval, $|f^{\prime \prime }|<3$ and $f^{\prime }>5$, so the stated quadratic convergence bound gives, with $e_n=|x_n-x^{\ast }|$,Iterating the bound givesThus four Newton corrections suffice to reduce the exact-iteration error bound below the floating-point spacing scale. The quadratic convergence doubles the approximate number of correct digits at each late step. Beyond this point further corrections cannot reliably improve a generic floating-point answer. This is a bound on useful accuracy under the usual stable-evaluation model, not a claim that the data specify the exact iteration at which every implementation must stagnate.

Minimize the square of the Euclidean distance, using minimizers under strictly increasing transformations. For $s=x+y>0$,For fixed $s$ the unique minimum has $x=y=s/2$. Put $x=y=\alpha >0$ and $J(\alpha )=2{\alpha }^2+{\ln }^2(2\alpha )$. Its derivative isLet $h(\alpha )=2{\alpha }^2+\ln (2\alpha )$. Since $h^{\prime }(\alpha )=4\alpha +1/\alpha >0$, it is strictly increasing, with limits $-\infty$ and $+\infty$ at the two ends of $(0,\infty )$. It therefore has exactly one zero. The sign of $J^{\prime }$ changes there from negative to positive, proving the unique global minimum. The nearest point is $P=(\alpha ,\alpha ,\ln (2\alpha ))$ at that zero.^[ref]

The Newton root-finding iteration isStarting at $0.4$ gives $0.376376476$, $0.376544572$, and $0.376544582$. Moreover $h(0.3765)<0<h(0.3766)$ certifies the rounding. Thus $\alpha =0.377$ to three significant figures; more accurately $P\approx (0.3765445825,0.3765445825,-0.2835716452)$.

Convexity of the components of a vector field is not the decisive criterion for a root-finding problem. Neither method becomes globally reliable merely because each component is convex.

Prefer the Newton root-finding iteration when the Jacobian matrix is available accurately and at reasonable cost. Solve $J({\mathbf{x}}_k){\mathbf{s}}_k=-\mathbf{f}({\mathbf{x}}_k)$ rather than explicitly forming an inverse matrix. Near a root with a nonsingular Jacobian matrix and a locally Lipschitz Jacobian matrix, the usual exact iteration has quadratic convergence.

Prefer Broyden's method when evaluating or differentiating the vector field makes a fresh Jacobian matrix expensive. It learns an approximate Jacobian matrix through secant updates using function differences. Under appropriate local regularity and initialization assumptions it has superlinear convergence, generally slower asymptotically than the quadratic convergence of exact Newton steps, but often with cheaper iterations.^[ref]

Dimension matters through storage and solves. A full dense Newton factorization costs order $d^3$ arithmetic operations; a dense Broyden approximation uses order $d^2$ storage, and maintained inverse or factorization updates can cost order $d^2$. A naive fresh dense solve can still cost order $d^3$. Sparsity can favour Newton, while very large $d$ can make either dense formulation unsuitable. Neither local rate guarantees convergence from an arbitrary starting point.

The Newton root-finding iteration isIt requires $f$ and its derivative to be defined at the current point, and requires $f^{\prime }(x)\ne 0$. A step can leave the domain, making a subsequent iteration undefined. In floating-point arithmetic, division by zero, overflow or non-finite function evaluations can also prevent a usable step. At a root where $f^{\prime }$ is zero the displayed quotient itself remains undefined unless the implementation stops before evaluating it.

The Newton root-finding iteration gives $x_1=0-(-1000)/1=1000$.

Set $h=x_{n+1}-x_n=-f(x_n)/f^{\prime }(x_n)$. By Taylor's theorem,The first two terms cancel by the definition of the Newton root-finding iteration. Thuswith $\xi$ between the consecutive iterates. In particular, a nonzero step has negative new residual under the stated strict concavity.

An iteration converges at least quadratically to a limit if its errors eventually satisfy the displayed bound with a fixed finite $C>0$. If $C{e}_N<1$, induction gives $|e_{N+k}|\le C^{-1}(C|e_N|{)}^{2^k}$. Exact asymptotic quadratic convergence has $|e_{n+1}|/|e_n{|}^2\to c\in (0,\infty )$. Newton root-finding iteration at a simple scalar root has this order when the second derivative at the root is nonzero; if that derivative vanishes, convergence can be faster.

Near a well-conditioned simple root, a numerically stable Newton root-finding iteration cannot usually resolve steps far below the local spacing of floating-point numbers. That spacing has relative scale comparable to machine epsilon $ϵ$, motivating the displayed position-based criterion with a modest constant $C$. It combines an absolute scale near zero with a relative scale for large inputs. A residual-only test is changed by rescaling the equation, whereas the root and exact Newton step are unchanged. A tiny step alone is not a universal accuracy certificate: derivative errors, stagnation and cycles require separate consideration.