Talk:Newton's method

Proof of quadratic convergence for Newton's iterative method

Does anyone think it's necessary to give a full proof of this as in the present version? It's possible to summarize it reasonably and convincingly in about two lines, and there are plenty of standard books to reference where the full proof appears. Gumshoe2 (talk) 14:28, 28 April 2024 (UTC)

I agree. Also, the preceding subsection is also confusing because of too much technical details. Imo, one must reduce the proofs and explanations to functions of class C2, with the simple mention that there are generalizations to slighty larger classes of functions. D.Lazard (talk) 16:12, 28 April 2024 (UTC)

Computable numbers

I'm removing the following paragraph:

When Newton's method can be applied to a transcendental equation, and converges to a solution of the equation, this implies that the solution is a computable number that is exactly represented by the pair formed by an initial approximation and an algorithm for increasing the accuracy of any approximation.

As stated, it seems definitely wrong. If c is an uncomputable number, then the root of x - c is c, and Newton's method initialized anywhere converges to the root (and even does so in a single step). Gumshoe2 (talk) 15:43, 28 April 2024 (UTC)

The paragraph becomes true if "transcentdental equation" is replaced with "equation defined by a computable function". This is the simplest way to prove that algebraic numbers are computable. D.Lazard (talk) 17:38, 28 April 2024 (UTC)

I don't know much on this topic, but the wikipage computable function suggests that the domain and range are only natural numbers, or tuples thereof. Is this the wrong context?

But it does make sense to me that Newton's method, along with other root-finding algorithms, can prove that algebraic numbers are computable. Is there a standard reference for this? I haven't been able to find it. Gumshoe2 (talk) 19:15, 28 April 2024 (UTC)

To editor Gumshoe2:Sorry, by trying to give sense to the removed paragraph, I did (wrong) original research. For computability with real numbers, one must look on the work by Stephen Smale and his followers. Also, for applying Newton's method to a transcendental equation, one requires to work with an increasing approximation of the equation and the involved derivatives. This seems to not be an easy task to define this propertly. This has probably been done in constructive mathematics, but I do not know this subject well.

By the way, in section § Multiplicative inverses of numbers and power series. it must be said that it is the quadratic convergence that insures that the computation of a multiplicative inverse has the same bit complexity as multiplication, even if fast multiplication is used (beacause of the quadratic convergence and the property of geometric series, all iterations but the last one take together no more time than the last iteration). This is also Newton's method that is used to show that matrix inversion has the same complexity as matrix multiplication, independently of the used multiplication algortihm. (As usual, I an unable to give references, but this should be found in most textbooks on complexity theory). D.Lazard (talk) 20:38, 30 April 2024 (UTC)

Systems of equations article draft

A draft article now exist for solving systems of equations, "Newton's method for systems of nonlinear equations". If approved, it should replace the existing sub-heading on the subject. While waiting for review, I would be helpful if interested parties were to weigh in with additional edits to the draft on subjects such as mathematical proofs, convergence theorems, etc. It will make a more credible draft and help with the review process. Netshine2 (talk) 01:50, 10 May 2024 (UTC)

Where is the draft available? I'm a little skeptical that it needs its own article, but certainly the present coverage should be expanded. Gumshoe2 (talk) 02:32, 10 May 2024 (UTC)

If someone wants to write one, I think this subject definitely can support its own article. There is a ton to say about it, enough to overflow 1–2 sections here. A new article would IMO be a much better solution than trying to generalize the first several sections of this article to cover all cases up front, but depending on the amount drafted, it could also remain a section. (I'm not sure whether a wordy explicit title would work better, or something more concise like Multivariate Newton's method.) –jacobolus (t) 02:51, 10 May 2024 (UTC)

I think there could be other solutions -- like you, I don't think the first several sections of this article should be generalized in place. I think it should be possible to more or less keep the present section layout on this page. But it all depends on the particular content in question.

As for titles, one issue is that, with the exception of freshman calculus texts, the "multivariate" Newton's method is the standard context that Newton's method is presented and used in. I think giving it a special page title like "Multivariate Newton's method" would make it appear unnecessarily niche. (Also see only 47 hits on Google Scholar for "multivariate Newton's method", 30 for "multivariable Newton's method") Gumshoe2 (talk) 03:06, 10 May 2024 (UTC)

If the consensus is to leave the Multivariate content in the current article, I am good with that. However, my thinking is that the Multivariate content will grow, and the existing article focuses heavily on single variable. The new draft article still needs an applications section, which I can contribute to, mathematical sections to prove out the details which math experts can contribute to, etc. Since, as you point out, half the draft article is already in the existing section, I can place the remainder in the existing section, too, at least until the new article issue is finalized. I am somewhat concerned that the remaining content, being primarily based on life experiences, may not meet verification standards, but we can try it. Any further thoughts on this subject?

As for the name, "Multivariate", the draft currently uses terminology from old text books. The theory still works, but naming conventions do change over time. I will update the draft to conform to current naming conventions. Netshine2 (talk) 15:58, 10 May 2024 (UTC)

To be clear: I have no deep insight or particular care about what title/terminology to use. I was just throwing out an idea of a more concise title. But a longer one can also be fine. –jacobolus (t) 16:47, 10 May 2024 (UTC)

Thank you for the suggestion. I liked it. I was unable to change the title in the draft, so I made a talk entry for it. Netshine2 (talk) 00:42, 11 May 2024 (UTC)

Seems to be at Draft:Newton's method for systems of nonlinear equations. –jacobolus (t) 02:58, 10 May 2024 (UTC)

I can comment later on the content, but I think that can all be well absorbed into this page. (The first half is already here.) Gumshoe2 (talk) 03:10, 10 May 2024 (UTC)

Example is not referenced.

The section under Multidimensional methods > Example has no sources. A recent edit by an IP user changed one number without any edit summary. Without any way to verify the content, I reverted the edit.

My change was reverted by @Netshine2 claiming that the IP user was correct. That's great, and I'm glad the content may now be correct. However we still have no way to verify it.

I think the content has marginal notability and absent a reference it may be a small kind of original research. Is there a case to keep this content? Johnjbarton (talk) 19:50, 29 May 2024 (UTC)

The references for the example would be the link to "Jacobian" matrix in the above section, and the multidimensional definition of Newton's method in the section above that. It is assumed that the derivatives in the example are covered by the reference to "Jacobian", since the Jacobian matrix is a matrix of partial derivatives.

The presence of the example serves to clarify the definitions in the section above. Users not familiar with Newton's method as it applies to actually doing something with it can easily see how the defining equations above work to obtain a valid converged solution. The equations are validated by keeping them simple and breaking them down into small enough pieces such that anyone skilled in Mathematics can validate the converging processes each step at a time. I do not believe the term "original research" really applies here because the example is simple to create and reproduce by anyone skilled in mathematics. The only challenge would be from user's not-so-skilled in mathematics, which is what the example is intended for. I have no objection to replacing the example with an existing published simple example, provided it is simple enough for users to follow, and complex enough for users to grasp the usefulness of Newton's method for multidimensional applications, but I have to point out that published example can contain typos, too. Netshine2 (talk) 20:21, 29 May 2024 (UTC)

Thanks! (please us the reply button on Talk pages). I made a minor edit to the reference.

 Done Johnjbarton (talk) 00:10, 30 May 2024 (UTC)

Looks Good! I'll have to remember the footnotes for future reference. Looks like we did good job of making the Wikipedia page better. 24.121.207.148 (talk) 00:27, 30 May 2024 (UTC)

I did some additional research and was able to find a published reference that used a similar example to ours, but it used 3 equations instead of our 2. For simplicity, I would prefer that our example keep the number of equations down to 2. Note that even if we were to use the reference example as-is, it still needs to be validated for typos and accuracy, which I very capable of doing. Please look the reference example, and let us know if you believe we should use it. The reference is easier to follow if you create a free account for yourself with the reference site. Netshine2 (talk)

Is "Convergence dependent on initialization" right?

By my calculations the result should be:

${\frac {-x_{n}^{2}}{2-x_{n}-2x_{n}^{2}}}\approx x_{n}\cdot {\frac {-x_{n}}{2}}$,

rather than x_n^3 . And the second paragraph does not add anything useful. So I would suggest removing the whole section. JRSpriggs (talk) 19:43, 6 May 2025 (UTC)

The derivation of the authors work is extremely tedious and easily prone to algebraic errors, at least for me. However, I used a computer program to compute the derivative digitally and plug the derivative result into the the rest of the equation, and was able to validate the author's result for x-F(x)/F'(x) for F(x)=x(1+x^2)^-.5 to be -x^3, as stated in the paragraph. Rather than bore the readers with all the derivation details that arrive at the solution, I think what is needed here is a footnote that goes through the derivation details. Netshine2 (talk) 22:26, 6 May 2025 (UTC)

Your calculations aren't right: if $f(x)={\frac {x}{(1+x^{2})^{1/2}}}$ then

$f'(x)={\frac {1}{(1+x^{2})^{3/2}}}$

so

$x-{\frac {f(x)}{f'(x)}}=x-x(1+x^{2})=-x^{3}.$

I don't support adding the details of calculation to the article, in a footnote or otherwise, since it's a routine calculation and not of any encyclopedic value.

I think the second paragraph is good as an example of extreme sensitivity to initial conditions, which is an important aspect of Newton iteration. Gumshoe2 (talk) 01:18, 7 May 2025 (UTC)

In that case, I would recommend removing the "[dubious – discuss]" note in the paragraph, but bear in mind the note appears to indicate that some readers may not be able to validate the expression as efficiently as we can, and may find it to be suspect. 24.121.207.148 (talk) 03:03, 7 May 2025 (UTC)

That tag was only added by JRSpriggs, there's no reason to think that any other readers are suspicious about it. I'll remove the tag and still think it would not be good to add these calculations to the page, footnote or otherwise. Gumshoe2 (talk) 04:33, 7 May 2025 (UTC)

Since

$f(x)=x\cdot (1-x^{2})^{-0.5}$.

Using the product rule, the rule for differentiating powers, and the chain rule, we get:

$f'(x)=1\cdot (1-x^{2})^{-0.5}+x\cdot -0.5\cdot (1-x^{2})^{-0.5-1}\cdot (0-2x)=(1-x^{2})^{-0.5}+x\cdot -0.5\cdot (1-x^{2})^{-1.5}\cdot -2x=(1-x^{2})^{-0.5}+x^{2}\cdot (1-x^{2})^{-1.5}=(1-x^{2}+x^{2})\cdot (1-x^{2})^{-1.5}=(1-x^{2})^{-1.5}$

Then

$x-{\frac {f(x)}{f'(x)}}=x-{\frac {x\cdot (1-x^{2})^{-0.5}}{(1-x^{2})^{-1.5}}}=x-(x\cdot (1-x^{2})^{-0.5}\cdot (1-x^{2})^{+1.5})=x-(x\cdot (1-x^{2})^{-0.5+1.5})=x-(x\cdot (1-x^{2})^{+1.0})=x-(x\cdot (1-x^{2}))=x-(x-x^{3})=x^{3}$.

So I was mistaken and the cube is OK after all. JRSpriggs (talk) 04:12, 7 May 2025 (UTC)

So, what is your opinion about placing your nice calculations in a footnote, given they are now complete and accurate? It may help improve the credibility of the paragraph and it may save other readers some time and headache. Netshine2 (talk) 04:19, 7 May 2025 (UTC)

I am sorry that I was forced by circumstances to log-off immediately after my previous post and was thus unable to revert my edit which put the "dubious" template into the section. I am happy to see that someone else removed it. If you want to put my newer calculation into a footnote, that would be fine with me. JRSpriggs (talk) 14:51, 7 May 2025 (UTC)

I think a derivation footnote would be a good addition for the more novice readers and would be happy to install it. However, I think we need more consensus, and do not yet have Gumshoe2 support. Gunshoe2, are you OK with placing JRSpriggs's nice derivation work into a foot note? Once we get your buy-off, I am happy to do the work. Netshine2 (talk) 15:01, 7 May 2025 (UTC)

No, I think it's way too much detail for an elementary computation. I've added one intermediate expression to the section, I think any more calculation detail than that would be inappropriate. Gumshoe2 (talk) 18:09, 7 May 2025 (UTC)

I think your middle step looks good. It will help give readers more confidence that the simple end result is valid, and will help those who attempt to derive the full solution. Netshine2 (talk) 18:16, 7 May 2025 (UTC)