Kyle.drerup

9/10/2010:

Homework 5:

11/9/2010

Problems I see with the article:

1. In several places, there are inconsistencies.

Bad Starting Points?

In the section called "Bad starting points", there is no mention of the assumptions made in the proof of quadratic convergence. These "bad starting points" do not meet the required assumptions, and this needs to be clarified.

Counterexamples

Every entry in the "counterexamples" section has a similar error. I will clean up this section, to state the reasons why the algorithm will not converge, and tie this section in with the proof of quadratic convergence.

2. Counterexamples? Is this a debate?

Calling that section "Counterexamples" is just a bad idea. It looks like this is a debate on the validity of Newton's Method.

3. Meaningless Statements

excerpt from Wikipedia:

 -Newton's method can often converge remarkably quickly, especially if the iteration begins "sufficiently near" the desired root.

define: Remarkably Quickly

 -answer:  fast enough to make passersby remark, "That one converges remarkably quickly."

What I'm getting at is this: The article contains lots of non-Quantitative useless information. The whole article needs some general cleanup on this front.

4. Generalizations:

The generalizations section is lacking.

I've got a little experience with Newton's in N-dimensions, with >= N equations.

I will expand this section, to include a code base for solving a system of nonlinear equations.

Project Report for User:Kyle.drerup

For Introduction to Numerical Analysis, Fall 2010.

Introduction

For my final project, I chose to improve the wikipedia article on Newton's Method. In general, the article needed a lot of cleanup. Additionally, I have some experience implementing this algorithm in 4 variables, and I thought I could add new and useful content to the Generalizations Section.

Initial Experience

Before engaging in the final project, I did a smaller project as part of some homework assignments.

I found the existing page on Loss of Significance unsatisfying. My largest concern with that page was the first example given. The example demonstrated the concept of loss of significance with decimal numbers, and with 20 digits. Although the example demonstrated the concept effectively, it seemed inaccessible to most people, due to the insane amount of digits displayed in it. It seemed like a better idea to describe it with binary numbers, using only a few digits. This would not confuse any readers, be easier on the eyes, and demonstrate what actually happens in the hardware of a binary computer.

I proposed to modify the example, demonstrating the concept with a binary number and only 10 digits.

My instructor pointed out some reasons to include a decimal example. The major reason was that some users might not be familiar with the concept of binary numbers. I agreed with this assessment, and decided to include the previous example later in the page.

I then posted my proposal to the discussion page on Loss of significance. I received some positive feedback, but not much.

I then posted my binary example on October 8, 2010, making sure to include the decimal example later in the page.

As of November 15, no further changes have been made to the Loss of Significance page.

Aditionally, while typing this page, I created a redirect page, sending [[Loss of Significance]] to [[Loss of significance]].

Main Project

Motivation

I found the page on Newton-Raphson Method disappointing. The |page as of Nov. 8 looks like this. I wouldn't use the term disrepair, but it was not looking too good. People had added their own little snippets to the bottoms of every section, and the whole page was disorganized.

Proposed Changes

Problems I saw with the page at the time are outlined here.

Actual Changes

1. First Paragraph

First, I clarified and reduced the first paragraph. It contained a lot of useless sentences with no meaning. I clarified it, to state who the method is named for, to state what it is used for, and to classify the method.

2. Practical Considerations

Second, I completely rewrote the Practical Considerations section.

The section was unorganized, wrong, and redundant in many places.

First, I deleted the errors.

The following is an excerpt form the page as of Nov. 8.

 -In these situations, it may be appropriate to approximate the derivative by using the slope of a line through 
  two points on the function. In this case, the Secant method results. This has slightly slower convergence than 
  Newton's method but does not require the existence of derivatives.

That is wrong. I won't give it the honor of explaining why.

Another error I found was the following:

 -Developers of large scale computer systems involving root finding tend to prefer the secant method over Newton's 
  method because the use of a difference quotient in place of the derivative in Newton's method implies that the 
  additional code to compute the derivative need not be maintained. In practice, the advantages of maintaining a 
  smaller code base usually outweigh the superior convergence characteristics of Newton's method.

That isn't really true. Newton's Method can be implemented with only a few lines of code. A robust implementation of newton's method can be a few dozen statements. It doesn't take much more code than the secant method, but it requires knowledge of Calculus. The possible failure of the method to converge to the root might be a reason not to implement the algorithm, but the amount of code should not be.

Next, I classified failures of the method as follows:

1.difficulty in calculating derivative of the function

2.failure of the method to converge

3.slow convergence of the method.

I tried to organize the information that was previously contained in the section into these three categories. By organizing the section in this way, we can look at the risks of failure, and organize the "practical considerations", or risk mitigation plans by the risks they mitigate. The section is by no means complete, and I'm not an expert on the subject, but I believe this new organization will be a permanent improvement. It should deter editors from adding little snippets to the bottom of the section, as was clearly happening before.

3. Basic definition of the algorithm

Third, I clearly labeled the definition of the algorithm for a single real variable. It was sort of growing out of the bottom of the first paragraph, and I just labeled it clearly, and stated that it was the single variable case.

4. Counterexamples ==> Failure Analysis

The section was called "counterexamples". I changed the title to "Failure Analysis", and I added a note at the top, stating that the failure of the method is caused by not meeting the assumptions made in the proof of Quadratic Convergence. This is important, so the reader understands the reasons for failure.

5. Generalizations: Newton-Raphson in n variables

Fourth, I made some major contributions to the Generalizations section.

I contributed to the section on nonlinear systems of equations. Specifically, I added a subsection on solving >k equations for k variables with a minimum of error.

I also wrote a matlab function to solve systems of nonlinear equations. The function solves k equations for k variables, or >k equations for k variables, minimizing error in the least-squares sense. In the past 2 days, the file has been downloaded 40 times.

Conclusions

I made some good contributions to the article. Much of the work I did was weeding out useless information, and organizing the existing information. I hope that my reorganization of the "practical considerations" section will deter future contributors from adding their information to the bottom of the section. I also hope that readers will understand that the method does not magically fail to converge for certain functions, but may fail to converge if the conditions needed for the proof of quadratic convergence are not met. I also hope that my source code is helpful to readers and users, and that my explanation of Newton's method with n variables is adequate. I believe my explanation on solving an overdetermined set of equations with minimal error is both correct and insightful, and I hope readers find it useful.

Even though I made some major contributions to this page, there is still a lot of work to be done. The page is by no means complete, nor is it perfectly organized. There is still a lot of work to be done.

I look forward to continuing my contributions to Wikipedia, and I hope to further improve not only the Newton-Raphson Method page, but others as well.